C. 移动括号

每次测试的时间限制：$1$ 秒
内存限制：$256$ 兆字节

给定一个长度为 $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$ 得到正则括号序列所需的最少移动次数。可以证明，在给定约束下答案总是存在的。

示例

输入：

4
2
)(
4
()()
8
())()()(
10
)))((((())

输出：

1
0
1
3

说明

在示例的第一个测试用例中，只需将第一个括号移动到字符串末尾即可。

在示例的第三个测试用例中，只需将最后一个括号移动到字符串开头即可。

在示例的第四个测试用例中，我们可以选择最后三个开括号，将它们移动到字符串开头，得到 "((()))(())"。