M. Deformed Balance
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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.

Example
Input
3
3
()(
1
)
7
(())())
Output
0
2
4
Note

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|$$$.