有一个括号序列，现在要计算一下它有多少非空子段是合法括号序列。
合法括号序列的定义是：
1. 空序列是合法括号序列。
2. 如果S 是合法括号序列，那么 (S)是合法括号序列。
3. 如果 A 和B 都是合法括号序列，那么 AB是合法括号序列。
本题包含多组测试数据。第一行输入一个整数 T，表示数据组数。
之后 T 行，每一行输入一个由'('和')'组成的串(可能有空串存在)，表示一个括号序列。
所有输入的括号序列的总长度不超过 10^6。
输出 T 行，每一行对应一个测试数据的答案。
5 ( () ()() (() (())
0 1 3 1 2
30%数据，t\leq 10,len(s)\leq 16
100%数据，t\leq 10^4,len(s)\leq 10^5
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |