Invertible Bracket Sequences

### 题意翻译 ### 题面描述 我们定义一个合法的括号序列，是仅由 `(` 和 `)` 构成的字符串且： 1. 空串 $\epsilon$ 是合法的括号序列。 2. 若 $s$ 为合法的括号序列，则 $(s)$ 也为合法的括号序列。 3. 若 $s,t$ 均为合法的括号序列，则 $st$ 也为合法的括号序列。（其中 $st$ 表示将字符串 $s$ 和 $t$ 拼接。） 定义对一个括号序列的**翻转**操作为：将这个括号序列的所有 `(` 变为 `)`，所有 `)` 变为 `(`。 如 `()(((` 翻转后成为 `)()))`。 给定一个**保证合法**的字符串 $s$。 你可以选择字符串 $s$ 的一个**子串**进行翻转操作。（注意是**子串**，与**子序列区分**，子串要求**连续**。） 问**翻转**了一个**子串**后得到的字符串 $s'$ 仍然是**合法括号序列**的方案数。 ### 输入格式 先是一个数字 $t$ 表示数据组数。 接下来 $t$ 行，每行一个合法括号序列 $s$。 ### 输出格式 对于每组数据，输出一个数字 $x$，表示翻转 $s$ 的一个子串后仍然是合法括号序列的方案数。 #### 说明 在本题中，不可以翻转长度为 $0$ 的子串。 translate by Hoks。

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.

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

1
0
3
13

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