You are given a string containing just the characters (, ), {, }, [and ]. Your task is to determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Input

• An interger ~N~ ~(N ≤ 10)~ is the number of testcases

• Each of the next ~N~ lines contains a string of only brackets ~S~ ~(0 ≤ |S| ≤ 10^4)~.

Output

• true if ~S~ is valid, otherwise false.

Sample Input 1

1
{[]}

Sample Output 1

true

Sample Input 2

2
([)]
{[]}

Sample Output 2

false
true