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