小泽拿到若干个由左、右括号组成的字符串。每个字符串中两种括号的数量相同。一次操作可以选择任意一个括号，将它从原位置删除并插入到字符串的任意位置。请求把字符串变成合法括号序列所需的最少操作次数。

输入格式

第一行是测试组数 $T$。每组先输入偶数 $N$，再输入长度为 $N$ 的括号串 $S$。

输出格式

对每组数据，输出最少操作次数。

3
4
(())
8
(())))((
12
(()))()(()()

0
2
1

1
2
)(

1

2
12
)(())())()((
6
()(())

2
0

数据范围与约定

• $1\le T\le2000$
• $2\le N\le50$
• $N$ 是偶数，两种括号各有 $N/2$ 个