CF1374C.Move Brackets

You are given a bracket sequence $s$ of length $n$, where $n$ is even (divisible by two). The string $s$ consists of $\frac{n}{2}$ opening brackets '(' and $\frac{n}{2}$ closing brackets ')'.

In one move, you can choose exactly one bracket and move it to the beginning of the string or to the end of the string (i.e. you choose some index $i$, remove the $i$-th character of $s$ and insert it before or after all remaining characters of $s$).

Your task is to find the minimum number of moves required to obtain regular bracket sequence from $s$. It can be proved that the answer always exists under the given constraints.

Recall what the regular bracket sequence is:

• "()" is regular bracket sequence;
• if $s$ is regular bracket sequence then "(" + $s$ + ")" is regular bracket sequence;
• if $s$ and $t$ are regular bracket sequences then $s$ + $t$ is regular bracket sequence.

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

You have to answer $t$ independent test cases.

给你一个长度为 $n$ 的括号序列 $s$，其中 $n$ 为偶数（即能被 $2$ 整除）。字符串 $s$ 恰好包含 $\frac{n}{2}$ 个左括号 '(' 和 $\frac{n}{2}$ 个右括号 ')'。

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

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

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

• "()" 是合法括号序列；
• 若 $s$ 是合法括号序列，则 "(" + $s$ + ")" 也是合法括号序列；
• 若 $s$ 和 $t$ 均为合法括号序列，则 $s + t$ 也是合法括号序列。

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

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 2000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($2 \le n \le 50$) — the length of $s$. It is guaranteed that $n$ is even. The second line of the test case containg the string $s$ consisting of $\frac{n}{2}$ opening and $\frac{n}{2}$ closing brackets.

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

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

For each test case, print the answer — the minimum number of moves required to obtain regular bracket sequence from $s$. It can be proved that the answer always exists under the given constraints.

对于每个测试用例，输出答案——将 $s$ 变为合法括号序列所需的最少操作次数。在给定约束条件下，可以证明答案一定存在。

In the first test case of the example, it is sufficient to move the first bracket to the end of the string.

In the third test case of the example, it is sufficient to move the last bracket to the beginning of the string.

In the fourth test case of the example, we can choose last three openning brackets, move them to the beginning of the string and obtain "((()))(())".

在示例的第一个测试用例中，只需将第一个括号移动到字符串末尾即可。

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

在示例的第四个测试用例中，我们可以选择最后三个左括号，将它们移动到字符串开头，从而得到 "((()))(())"。