合法匹配

括号序列指的是只包含 ‘(’ 和 ‘)’ 的序列。

合法括号序列的定义如下：
1.空序列为合法序列。
2.如果 $A$ 是一个合法序列，则 $(A)$ 也为合法序列。
3.如果 $A$ 和 $B$ 都为合法序列，则 $AB$ 也为合法序列。

现给出一个括号序列，求最少删去几个括号能得到一个合法序列。

第一行一个整数 $T(1 \leq T \leq 30)$ ，表示测试数据组数。接下来包含 $T$ 组测试数据。

对于每组测试数据，第一行输入一个整数 $n\ (1 \leq n \leq 2 \times 10^5)$ ，表示括号序列的长度。

第二行输入一个长为 $n$ 的括号序列。

对于每组测试数据，输出一个数表示最少删去几个括号能得到一个合法的括号序列。

2
6
()(())
7
())(()(

0
3

内蒙古自治区第十五届大学生程序设计竞赛