Given a string with the just the six characters - ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’. Determine if the string is balanced.

A string is balanced if all brackets exist in pairs and are closed in the correct order.

Example:

String: ({})[]

Result: Balanced

String: {()})(

Result: Not Balanced

String: {(})[]

Result: Not Balanced

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case, a line containing a parentheses string.

Output Format

For each test case, a line containing 1 or 0 if the string is valid or not respectively.

Sample Input 

3
({})[]
{()})(
{(})[]

Expected Output

1
0
0

Constraints

1 <= T <= 100
1 <= String Length <= 104