题目描述

给定一个长度为 $n$ 的括号序列 $s$。$n$ 为偶数，且 $s$ 中恰好有 $\frac n2$ 个左括号 ( 和 $\frac n2$ 个右括号 )。

一次操作中，你可以任选一个括号，把它从原位置删除，再放到整个字符串的开头或结尾。求最少操作次数，使 $s$ 变成一个合法括号序列。题目保证在给定条件下总能做到。

合法括号序列的定义如下：

• () 是合法括号序列；
• 若 $s$ 是合法括号序列，则 ( + $s$ + ) 也是合法括号序列；
• 若 $s,t$ 都是合法括号序列，则 $s+t$ 也是合法括号序列。

例如，()()、(())()、(()) 和 () 都是合法括号序列；)(、()( 和 ))) 都不是。

需要独立回答 $t$ 组测试数据。

输入格式

第一行一个整数 $t$（$1\le t\le2000$），表示测试组数。

每组数据第一行一个偶数 $n$（$2\le n\le50$），表示字符串长度；第二行一个长度为 $n$ 的字符串 $s$，其中恰有 $\frac n2$ 个 ( 和 $\frac n2$ 个 )。

输出格式

对每组数据输出一个整数，表示把 $s$ 变为合法括号序列所需的最少操作次数。

样例

样例 1

输入：

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

输出：

1
0
1
3