Minimum Parentheses Addition for Valid String

You are given a string s consisting of only the characters (' and ')'. The task is to determine the minimum number of parentheses that need to be added to s to make it a valid (i.e. balanced) parentheses string.

A string is considered valid if each opening parenthesis has a corresponding closing parenthesis in the correct order. For example, the string "()" is valid, while "(()" and "())" are not.

Input/Output Instructions: Your program should read input from stdin and write the result to stdout. The first line of the input contains an integer T, the number of test cases. Each of the following T lines contains a single string comprised exclusively of '(' and ')' characters. For each test case, output the minimum number of parentheses that must be added to make the string balanced.

Examples:

• Example 1: Input: 3\n())(\n(((\n))) Output: 2\n3\n3
• Example 2: Input: 5\n\n()\n(())\n(()))\n((()) Output: 0\n0\n0\n1\n1
• Example 3: Input: 1\n()(())) Output: 1

inputFormat

The first line contains an integer T, indicating the number of test cases. The next T lines each contain a non-empty string s consisting only of the characters '(' and ')'. Note that s can be an empty string as well.

outputFormat

Output T lines, where the i-th line contains an integer representing the minimum number of parentheses that need to be added to the i-th test case string to make it valid.

## sample

3
())(
(((
)))

2
3
3

</p>