311376: CF1976D. Invertible Bracket Sequences

D. Invertible Bracket Sequencestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

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.

ExampleInput

4
(())
()
()()()
(()())(())

Output

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$ (()());

题目大意：
给定一个合法的括号序列，计算有多少对整数(l, r)（1≤l≤r≤|s|），使得将s的第l个字符到第r个字符（包括）的子串替换为其逆序列后，s仍然是一个合法的括号序列。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例仅包含一行，为一个非空的合法括号序列，只由字符'('和/or ')'组成。
所有测试用例的括号序列总长度不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数——满足题目条件的整数对(l, r)的数量。

示例：
输入：
4
(())
()
()()()
(()())(())

输出：
1
0
3
13题目大意： 给定一个合法的括号序列，计算有多少对整数(l, r)（1≤l≤r≤|s|），使得将s的第l个字符到第r个字符（包括）的子串替换为其逆序列后，s仍然是一个合法的括号序列。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例仅包含一行，为一个非空的合法括号序列，只由字符'('和/or ')'组成。 所有测试用例的括号序列总长度不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——满足题目条件的整数对(l, r)的数量。 示例： 输入： 4 (()) () ()()() (()())(()) 输出： 1 0 3 13