常规括号序列是通过在序列的原始字符之间插入字符“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)$$$ 对的数量。
示例
输入 #1
4 (()) () ()()() (()())(())
输出 #1
1 0 3 13
注意
在第一个示例中,只有一对:
- $$$(2, 3)$$$: (()) $$$\rightarrow$$$ ()()。
在第二个示例中,没有对。
在第三个示例中,有三对:
- $$$(2, 3)$$$: ()()() $$$\rightarrow$$$ (())();
- $$$(4, 5)$$$: ()()() $$$\rightarrow$$$ ()(());
- $$$(2, 5)$$$: ()()() $$$\rightarrow$$$ (()());