给您一个由 $$$n$$$ 字符“(”和/或)'组成的括号序列。您可以使用它执行多项操作。
在一次操作期间,您选择该字符串的最短前缀(字符串的一些第一个字符),并将其从字符串中删除。
如果满足以下两个条件之一,则认为该前缀是好的:
- 该前缀是常规括号序列;
- 该前缀是长度至少为 2 的回文。
如果可以通过在序列中插入字符“+”和“1”来获得正确的算术表达式,则该序列称为正则括号序列。例如,序列 (())()、() 和 (()(())) 是规则的,而 )(、(() 和 (()))( 则不是。
如果括号序列来回读取相同,则称为回文。例如,括号序列 ))、(( 和 )(() 是回文,而括号序列 ()、)( 和 ))( 不是回文。
当无法找到好的前缀时,您将停止执行操作。您的任务是查找将对给定字符串执行的操作数以及字符串中剩余的字符数。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行描述了测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 括号序列的长度。
测试用例的第二行包含 $$$n$$$ 字符“(”和/或“)”——括号序列本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$ ($$$\sum n \le 5 \cdot 10^5$$$)。
输出
对于每个测试用例,打印两个整数 $$$c$$$ 和 $$$r$$$ — 您将对给定括号序列执行的操作数以及执行所有操作后字符串中保留的字符数。
示例
输入 #1
5 2 () 3 ()) 4 (((( 5 )((() 6 )((()(
输出 #1
1 0 1 1 2 0 1 0 1 1