Problem M

Deformed Balance

Time limit: 2 seconds

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 “(” \(+\, T \,+\) “)”, 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 \,+\) “)” \(+\, U\), where \(T\) and \(U\) are deformed strings.
The concatenation “(” \(+\, T \,+\) “(”, 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 \,+\) “)” 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\)).

Input

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\).

Output

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

Sample Input #1

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

Sample Output #1

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|\).