题目描述

给定一个长度为 $n$ 的括号序列 $s$，其中 $n$ 是偶数（能被 $2$ 整除）。字符串 $s$ 由 $\frac{n}{2}$ 个左括号 '(' 和 $\frac{n}{2}$ 个右括号 ')' 组成。

每次操作，你可以选择恰好一个括号，将其移动到字符串的开头或结尾（即选择某个下标 $i$，移除 $s$ 的第 $i$ 个字符，并将其插入到剩余字符串的最前面或最后面）。

你的任务是求出将 $s$ 变为合法括号序列所需的最少操作次数。在给定的约束下，可以保证一定存在解。

回忆一下什么是合法括号序列：

• "()" 是合法括号序列；
• 如果 $s$ 是合法括号序列，则 "(" + $s$ + ")" 也是合法括号序列；
• 如果 $s$ 和 $t$ 都是合法括号序列，则 $s$ + $t$ 也是合法括号序列。

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

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

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 2000$），表示测试用例的数量。接下来有 $t$ 组测试用例。

每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 50$），表示 $s$ 的长度。保证 $n$ 是偶数。第二行包含一个字符串 $s$，由 $\frac{n}{2}$ 个左括号和 $\frac{n}{2}$ 个右括号组成。

输出格式

对于每组测试用例，输出一个整数，表示将 $s$ 变为合法括号序列所需的最少操作次数。在给定的约束下，答案一定存在。

说明/提示

在第一个样例中，只需将第一个括号移动到字符串末尾即可。

在第三个样例中，只需将最后一个括号移动到字符串开头即可。

在第四个样例中，可以选择最后三个左括号，将它们移动到字符串开头，得到 "((()))(())"。

由 ChatGPT 4.1 翻译

样例

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

1
0
1
3