Balanced Brackets

In this problem, you are given a number of bracket sequences. A sequence is considered balanced if it meets the following criteria:

• Every opening bracket (, [, or { has a corresponding closing bracket ), ], or }.
• The pairs of brackets are properly nested. For example, ([{ }]) is valid while (]{[}) is not.

Your task is to determine whether each bracket sequence is balanced. If a sequence is balanced, print YES, otherwise print NO.

The problem can be mathematically reasoned using a stack. A sequence S with length L is balanced if and only if \[ \text{if } S_i \text{ is an opening bracket then push it, and if } S_i \text{ is closing then } S_i \text{ must correspond to the last pushed opening bracket}. \]

inputFormat

The input is read from standard input (stdin) with the following format:

N
sequence_1
sequence_2
... 
sequence_N

Where N is an integer representing the number of sequences, followed by N lines each containing a bracket sequence.

outputFormat

For each bracket sequence, output a line with either YES if the sequence is balanced, or NO otherwise.

Output is written to standard output (stdout).

## sample

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

YES
NO
YES

</p>