给定一个长度为 $$$n$$$ 的括号序列 $$$s$$$,其中 $$$n$$$ 是偶数(可被二整除)。字符串 $$$s$$$ 由 $$$\frac{n}{2}$$$ 左括号 '(' 和 $$$\frac{n}{2}$$$ 右括号 ')' 组成。
在一次移动中,您可以精确选择一个括号并将其移动到字符串的开头或字符串的末尾(即,您选择某个索引 $$$i$$$,删除 $$$s$$$ 的第 $$$i$$$ 个字符,并将其插入到 $$$s$$$ 的所有剩余字符之前或之后)。
你的任务是找到从 $$$s$$$ 中获得规则括号序列所需的最少移动次数。可以证明,在给定的约束条件下,答案总是存在的。
回想一下常规括号序列是什么:
- “()”是常规括号序列;
- 如果 $$$s$$$ 是常规括号序列,则 "(" + $$$s$$$ + ")" 是常规括号序列;
- 如果 $$$s$$$ 和 $$$t$$$ 是常规括号序列,则 $$$s$$$ + $$$t$$$ 是常规括号序列。
例如,“()()”、“(())()”、“(())”和“()”是常规括号序列,但“)(”、“()(”和“)))”则不是。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — $$$s$$$ 的长度。保证 $$$n$$$ 是偶数。测试用例的第二行包含字符串 $$$s$$$,由 $$$\frac{n}{2}$$$ 左括号和 $$$\frac{n}{2}$$$ 右括号组成。
输出
对于每个测试用例,打印答案 - 从 $$$s$$$ 获取常规括号序列所需的最少移动次数。可以证明,在给定的约束条件下,答案总是存在的。
示例
输入 #1
4 2 )( 4 ()() 8 ())()()( 10 )))((((())
输出 #1
1 0 1 3
注意
在示例的第一个测试用例中,将第一个括号移动到字符串的末尾就足够了。
在示例的第三个测试用例中,将最后一个括号移动到字符串的开头就足够了。
在示例的第四个测试用例中,我们可以选择最后三个左括号,将它们移动到字符串的开头并获得“((()))(())”。