01204212/paren

from 01204212

You have a string consisting of parentheses ( ), curly braces { }, and brackets [ ]. You want to check if they are properly balanced. The following are examples of balanced strings:

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

These are unbalanced strings:

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

You want to write a program that performs the balance checking.

Input/Output

Input

The first line: an integer T, the number of test cases. The next T lines: each line contains a string representing each test case.

Output

For each test case, output either yes if the string is balanced, and no if the string is not balanced.

Example

Input

5
()()(())
((((
[[](){{}}]
[][][]()(){}
[[{]}]

Output

yes
no
yes
yes
no