codeforces#P1976D. Invertible Bracket Sequences

    ID: 34687 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchcombinatoricsdata structuresimplementationtwo pointers

Invertible Bracket Sequences

Description

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example:

  • bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
  • bracket sequences ")(", "(" and ")" are not.

Let's define the inverse of the bracket sequence as follows: replace all brackets '(' with ')', and vice versa (all brackets ')' with '('). For example, strings "()((" and ")())" are inverses of each other.

You are given a regular bracket sequence $s$. Calculate the number of pairs of integers $(l,r)$ ($1 \le l \le r \le |s|$) such that if you replace the substring of $s$ from the $l$-th character to the $r$-th character (inclusive) with its inverse, $s$ will still be a regular bracket sequence.

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains a non-empty regular bracket sequence; it consists only of characters '(' and/or ')'.

Additional constraint on the input: the total length of the regular bracket sequences over all test cases doesn't exceed $2 \cdot 10^5$.

For each test case, print a single integer — the number of pairs $(l,r)$ meeting the conditions from the statement.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains a non-empty regular bracket sequence; it consists only of characters '(' and/or ')'.

Additional constraint on the input: the total length of the regular bracket sequences over all test cases doesn't exceed $2 \cdot 10^5$.

Output

For each test case, print a single integer — the number of pairs $(l,r)$ meeting the conditions from the statement.

4
(())
()
()()()
(()())(())
1
0
3
13

Note

In the first example, there is only one pair:

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

In the second example, there are no pairs.

In the third example, there are three pairs:

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