Description

You are given n string, each string S_i consisting of parentheses '(', ')', '[' and ']'.
A string S is said to be correct if:
1. S is the empty string
2. A and B are correct, S = AB
3. A is correct, S = (A) or S = [A]

Judge each of n string is correct or not.

If yes, please output the number of pairs of bracket in the expression.

Otherwise, output 0.

Input

The first line contains an integer n — the total number of string you have to judge it is correct or not.

Each of the following n lines contains a string S_i.

Restrictions

For test ID 1 (each 20 points):

• 1 ≤ n ≤ 10
• 1 ≤ |S_i| ≤ 10²

For test ID 2-5 (each 20 points):

• 1 ≤ n ≤ 10³
• 1 ≤ |S_i| ≤ 10⁴

Output

For each string, output one line following problem description.

Sample Input  Download

Sample Output  Download

Tags

Discuss