CourseGrading

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

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

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

输入

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

每组测试数据占两行。

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

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

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

输入

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

输出

1
0
3

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

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

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