Balance Parentheses

You are given a list of strings, each consisting solely of the characters '(' and ')'. For each string, determine the minimum number of modifications (insertions or deletions) required to make the string of parentheses balanced.

A string is considered balanced if:

• The total number of opening and closing parentheses is equal.
• At any prefix of the string, the number of closing parentheses does not exceed the number of opening parentheses.

Formally, for a given string S, let open_count be the number of unmatched '(' and fix be the number of unmatched ')' encountered. The result is given by:

$$result = open\_count + fix$$

inputFormat

The input is read from standard input (stdin). The first line contains a single integer T, the number of test cases. Each of the following T lines contains a string consisting solely of the characters '(' and ')'.

outputFormat

For each test case, output a single line containing one integer: the minimal number of modifications required to balance the parentheses in that string.

## sample

5
(()))
(((
(())
)(
()

1
3
0
2
0

</p>