Minimum Parentheses to Balance

You are given a string consisting solely of the characters '(' and ')'. Your task is to determine the minimum number of parentheses that must be added to the string so that the resulting sequence is balanced. A balanced string obeys the following rule:

\( \text{For every prefix of the string, the number of '(' is at least as many as the number of ')'} \)

and the total number of '(' equals the total number of ')'.

For example, given the input string "(()", one additional ')' is needed to balance the string.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer \( T \) denoting the number of test cases.
• Each of the next \( T \) lines contains a single string consisting of only '(' and ')'.

outputFormat

For each test case, output a single line containing one integer: the minimum number of parentheses required to add so that the given string becomes balanced.

## sample

3
()
)(
(()

0
2
1

</p>