CF2206M Deformed Balance

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.

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