Valid Parentheses Checker

This problem involves checking whether a string composed of characters '(', ')', '[', ']', '{', and '}' forms a valid sequence of matched parentheses. A string is considered valid if:

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets are closed in the correct order.

Formally, you must determine, for a given string \( s \), if it is valid. The validity rules can be summarized as follows:

• If \( s = \epsilon \) (the empty string), then it is valid.
• If \( s = A \oplus B \) (concatenation of A and B) is valid provided both A and B are valid.
• If \( s = \{(s')\} \) (or with parentheses/brackets) is valid provided \( s' \) is valid.

Your task is to read multiple test cases from stdin where the first line contains an integer \( T \) (the number of test cases), followed by \( T \) lines each containing a string consisting solely of the characters mentioned above. For each test case, output "YES" if the string is valid or "NO" if it is not.

inputFormat

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

T
s1
s2
... 
sT

Where:

• \( T \) is the number of test cases.
• Each \( s_i \) is a string containing only brackets: '(', ')', '[', ']', '{', and '}' (possibly an empty string).

outputFormat

For each test case, print a single line to stdout containing either "YES" if the input string is valid or "NO" if it is not.

## sample

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

YES
YES
NO

</p>