In this problem, a concatenation of two strings and is denoted by .
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 , where 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 , where and are deformed strings.
The concatenation , where is a deformed string.
For example, "()(" and "))()(" are deformed, while "()" and "(()" are not.A string has a deformed balance if is deformed and the concatenation is balanced. For example, the string "()(" has a deformed balance.
You are given a string of length consisting only of parentheses. Under the given input constraints, it can be shown that there exist strings and such that the concatenation has a deformed balance. Determine the minimum possible value of (the sum of the lengths of and ).
输入格式
The first line of input contains one integer ( ) representing the number of test cases. After that, test cases follow. Each of them is presented as follows.
The first line of each test case contains an integer ( ).
The second line contains a string of length , consisting only of '(' or ')'.
The sum of across all test cases in one input file does not exceed .
输出格式
For each test case, output the minimum possible value of such that the concatenation has a deformed balance.
样例
样例输入 1
3
3
()(
1
)
7
(())())
样例输出 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 and to "(" yields the concatenation "()(", which has a deformed balance. The value of is .
For the third test case, it suffices to set to "((()" and to an empty string to attain the minimum value of .
