A82881.移动括号

给你一个只由左括号 ( 和右括号 ) 组成的字符串 $s$，长度为 $n$，并且 $n$ 是偶数；同时 $s$ 里有一半是左括号、另一半是右括号。

一次操作你可以：

• 选取字符串里的一个括号，把它挪到最前面或者最后面。

问：把 $s$ 变成合法括号序列，至少需要多少次操作？

合法括号序列的定义：

• "()" 是合法；
• 如果 $x$ 是合法，那么 "(" + x + ")" 也是合法；
• 如果 $x,y$ 都合法，那么 x + y 也合法。
  例如："()()"、"(())"、"(())()" 都合法；而 ")("、"()(" 不合法。

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

• 第一行：一个整数 $t$，表示测试组数。
• 每组测试包含两行：
  • 第一行：一个偶数 $n$（$2 \le n \le 50$）；
  • 第二行：一个长度为 $n$ 的括号串 $s$，其中 ( 和 ) 的数量各为 $n/2$。

• 对每组测试，输出一行一个整数：把 $s$ 变成合法括号序列的最少操作次数。

数据范围

• $1 \le t \le 2000$
• $2 \le n \le 50$，$n$ 为偶数
• $s$ 中 ( 和 ) 的数量相等

样例解释

• ")("：把第一个 ) 移到串尾，得到 "()"，1 次。
• "()()"：本来就是合法，0 次。
• "())()()("：把最后一个 ( 挪到最前面即可，1 次。
• ")))((((())"：移动 3 次可变合法。