D. Инвертируемые скобочные последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы '1' и '+' между исходными символами. Например:

  • скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
  • скобочные последовательности «)(», «(» и «)» — неправильные.

Давайте определим инверсию скобочной последовательности следующим образом: заменить все скобки '(' на ')', и наоборот (все скобки ')' на '('). Например, строки «()((» и «)())» являются инверсиями друг друга.

Задана правильная скобочная последовательность $$$s$$$. Ваша задача — посчитать количество таких пар целых чисел $$$(l,r)$$$ ($$$1 \le l \le r \le |s|$$$), что если заменить всю подстроку $$$s$$$ с $$$l$$$-го символа по $$$r$$$-й символ (включительно) на ее инверсию, $$$s$$$ все еще будет правильной скобочной последовательностью.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит непустую правильную скобочную последовательность; она состоит только из символов '(' и/или ')'.

Дополнительное ограничение на входные данные: общая длина правильных скобочных последовательностей по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество пар $$$(l,r)$$$, удовлетворяющих условию задачи.

Пример
Входные данные
4
(())
()
()()()
(()())(())
Выходные данные
1
0
3
13
Примечание

В первом примере есть только одна пара:

  • $$$(2, 3)$$$: (()) $$$\rightarrow$$$ ()().

Во втором примере подходящих пар нет.

В третьем примере есть три подходящих пары:

  • $$$(2, 3)$$$: ()()() $$$\rightarrow$$$ (())();
  • $$$(4, 5)$$$: ()()() $$$\rightarrow$$$ ()(());
  • $$$(2, 5)$$$: ()()() $$$\rightarrow$$$ (()());