Balanced Brackets

You are given several sequences of brackets. Your task is to determine if each sequence is balanced or not.

A sequence of brackets is considered balanced if every opening bracket has a corresponding closing bracket in the correct order. The valid brackets are (), [], and {}.

More formally, a sequence is balanced if it can be written in the form: \[ S \rightarrow \epsilon \;|\; (S) \;|\; [S] \;|\; {S} \;|\; SS \] where \(\epsilon\) denotes the empty string.

You need to process multiple sequences from the input and output YES for a balanced sequence and NO otherwise.

inputFormat

The input is read from stdin and has the following format:

1. An integer T (1 ≤ T ≤ 1000), the number of test cases.
2. Then T lines follow, each line is a non-empty string consisting of brackets ('(', ')', '[', ']', '{', '}').

Note: The string can be empty, which is considered balanced.

outputFormat

For each test case, print a line with the output YES if the sequence is balanced, or NO otherwise. The output should be written to stdout.

## sample

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

YES
YES
YES
NO
NO
NO

</p>