3148. 这货不是括号匹配

给定一个长度为 的括号序列 ,其中保证 是偶数。字符串 个左括号和 个右括号组成。

你每次操作可以选择 中任意一个括号,将其移动到字符串开头或者末尾。

询问使 符合括号匹配规则的最少操作次数。


输入

第一行输入一个整数 ,表示接下来有 组测试数据。

每组测试数据占两行。

每组第一行输入一个整数 ,表示 的长度。

每组第二行输入一个长度为 的字符串 ,意义如题面所述。


输出

对于每组测试数据,输出一个整数,表示实现括号匹配的最少操作次数。


样例

输入

3
2
)(
6
(())()
10
)))((())((

输出

1
0
3


说明

在第一个样例中,将第一个括号移动到末尾即可实现。

在第二个样例中,无需进行任何操作。

在第三个样例中,将前三个括号移动到末尾可以获得字符串 ((())(())) 符合括号匹配规则。


难度等级: 0
总通过次数: 160
总提交次数: 350