题目描述

In this problem, a concatenation of two strings $T$ and $U$ is denoted by $T+U$ .

A string consisting only of parentheses (opening parentheses '(' or closing parentheses ')') is balanced if and only if it is one of the following.

• An empty string.
• The concatenation of two non-empty balanced strings.
• The concatenation $\texttt{(} + T + \texttt{)}$ , where $T$ is a balanced string.

For example, "()" and "(())()" are balanced, while "()(" and "((()" are not.A string is deformed if and only if it is one of the following.

• The string ")".
• The concatenation $T + \texttt{)} + U$ , where $T$ and $U$ are deformed strings.
• The concatenation $\texttt{(} + T + \texttt{(}$ , where $T$ is a deformed string.

For example, "()(" and "))()(" are deformed, while "()" and "(()" are not.A string $T$ has a deformed balance if $T$ is deformed and the concatenation $T + \texttt{)}$ is balanced. For example, the string "()(" has a deformed balance.

You are given a string $S$ of length $n$ consisting only of parentheses. Under the given input constraints, it can be shown that there exist strings $X$ and $Y$ such that the concatenation $X + S + Y$ has a deformed balance. Determine the minimum possible value of $|X| + |Y|$ (the sum of the lengths of $X$ and $Y$ ).

输入格式

The first line of input contains one integer $t$ ( $1 \le t \le 10\,000$ ) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of each test case contains an integer $n$ ( $1 \le n \le 10^6$ ).

The second line contains a string $S$ of length $n$ , consisting only of '(' or ')'.

The sum of $n$ across all test cases in one input file does not exceed $10^6$ .

输出格式

For each test case, output the minimum possible value of $|X|+|Y|$ such that the concatenation $X + S + Y$ has a deformed balance.

3
3
()(
1
)
7
(())())

0
2
4

提示

Explanation for the sample input/output #1

For the first test case, the given string already has a deformed balance.

For the second test case, setting both $X$ and $Y$ to "(" yields the concatenation "()(", which has a deformed balance. The value of $|X|+|Y|$ is $2$ .

For the third test case, it suffices to set $X$ to "((()" and $Y$ to an empty string to attain the minimum value of $|X|+|Y|$ .