Pipes

We define a valid parenthesization S as a string that contains symbols from the alphabet Σ = "{}[]()|" and is constructed based on the rules:

• S = "(" + some valid parenthesization + ")"
• S = "[" + some valid parenthesization + "]"
• S = "{" + some valid parenthesization + "}"
• S = "|" + some valid parenthesization + "|"
• S = some valid parenthesization + some other valid parenthesization

The empty string is also considered valid.

Your task is to determine whether some given parenthesizations are valid.

Input

The first line of input contains an integer N.
Each of the following N lines contains a string S, constructed out of symbols from the aforementioned alphabet.

Output

For each given string, output YES if it is a valid parenthesization, NO otherwise. Answers should be newline-separated.

Constraints

• 1 ≤ N ≤ 10
• 1 ≤ |S| ≤ 4000

Sample