You are given a string consisting of parentheses ( ) and [ ]. A string of this type is said to be correct:

• if it is the empty string
• if A and B are correct, AB is correct,
• if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input

The first line contains the number of test cases n. Each of the next n lines contains the string of parentheses ( ) and [ ].

Output

For each test case print in a separate line "Yes" if the expression is correct or "No" otherwise.