Given a string of parentheses, we must turn it into a well formed string by changing as few characters as possible (we cannot delete or insert characters).

There are 3 kinds of parentheses: regular (), brackets [] and curly brackets {}. Each pair has an opening ('(', '[' and '{' respectively) and a closing (')', ']' and '}') character.

A well formed string of parentheses is defined by the following rules:

* The empty string is well formed.
* If s is a well formed string, (s), [s] and {s} are well formed strings.
* If s and t are well formed strings, the concatenation st is a well formed string.
As examples, "([{}])", "" and "(){}[]" are well formed strings and "([}]", "([)]" and "{" are malformed strings.

Given a String s of parentheses, return the minimum number of characters that need to be changed to make it into a well formed string.

Notes
- Changing a character is selecting one position in the string and changing the character in that position to any other parentheses character.
Constraints
- s will have between 0 and 50 characters, inclusive.
- s will have an even number of characters.
- Each character of s will be '(', '[', '{', ')', ']' or '}'.

Input Format :
Line1 - No of test cases T (<50)
Next T lines contain String of parentheses for T test cases.

Output Format
Line 1 to T - Each line contain Required Number for the corresponding test case.

Examples
0)
([{}])()[]{}
Returns: 0
This is already well formed.

1)
([)]
Returns: 2
With two changes you can get "([])" (there are other ways with the same number of changes).

2)
([{}[]
Returns: 1
Simply changing the second character will give you "(){}[]".