括号
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
dXqwq 和 Haitang 在玩一个括号串上的游戏。
有一个初始全为黑色的括号串 S，两个人各有一把刷子，dXqwq 的刷子是红色的，Haitang 的刷子是蓝色的。
她们会依次执行以下操作，直到所有括号都被染色，且 dXqwq 先执行操作：
- 选择一个没有被染色的括号，用自己的刷子将它染色。
在操作后，dXqwq 会取出红色括号的一个可以匹配的子序列，并将其长度的一半定义为游戏分数。
dXqwq 希望最大化游戏分数，而 Haitang 则希望最小化这个值，你需要输出两人都在最优策略下操作后的游戏分数。
Input Format
从文件 bracket.in 中读入数据。
本题有多组测试数据。
第一行输入一个整数 T，代表数据组数。
接下来 T 行，每行输入一个括号串 S。
Output Format
输出到文件 bracket.out 中。
对于每组数据输出一行一个整数，代表最优策略下的游戏分数。
4
)(
(())
()()()()
(()(())())0
1
2
2Hint
样例
Input 1
4 )( (()) ()()()() (()(())())
Output 1
0 1 2 2
Input 2
见下发的 bracket2.in。 该样例满足测试点 5 的性质。
Output 2
见下发的 bracket2.ans。 该样例满足测试点 5 的性质。
Input 3
见下发的 bracket3.in。 该样例满足测试点 11 的性质。
Output 3
见下发的 bracket3.ans。 该样例满足测试点 11 的性质。
数据范围
本题共 20 个测试点，全部测试点满足 T=10，1≤∣S∣≤105，Si∈{(,)}。
下表记 N=max(∣S∣)。
| 测试点 | N≤ | 特殊限制 |
|---|---|---|
| 1 | 9 | 数据随机生成 |
| 2 | 9 | |
| 3 | 20 | 数据随机生成 |
| 4∼5 | 20 | |
| 6 | 105 | S 不存在子序列 () |
| 7∼8 | 100 | S 不存在子序列 )( |
| 9 | 105 | S 不存在子序列 )( |
| 10∼11 | 100 | 数据随机生成 |
| 12∼13 | 100 | |
| 14∼15 | 500 | 数据随机生成 |
| 16 | 500 | |
| 17 | 2×103 | 数据随机生成 |
| 18 | 2×103 | |
| 19 | 105 | 数据随机生成 |
| 20 | 105 |
数据随机生成：∣S∣=N，每个字符等概率为 (,) 中的一个。
样例解释
对于第一组样例，一种最优的决策过程如下：
- dXqwq 涂 S1，S=)(
- Haitang 涂 S2，S=)(
对于第二组样例，一种最优的决策过程如下：
- dXqwq 涂 S1，S=(())
- Haitang 涂 S3，S=(())
- dXqwq 涂 S4，S=(())
- Haitang 涂 S2，S=(())