Correctly Nested Brackets

You are given a sequence of brackets. Your task is to determine whether the brackets are correctly nested.

A sequence is considered correctly nested if each opening bracket has a corresponding closing bracket in the correct order. The valid bracket characters are (, ), [, ], {, and }.

For example, the sequence () and ([{}]) are correctly nested, while ([]{)} and ({[}]) are not.

The algorithm uses a stack to push every opening bracket and checks against the corresponding closing bracket. Formally, if we denote the set of opening brackets by \(O = \{ (, [, \{ \}\}\) and the corresponding closing brackets by \(C = \{ ), ], \} \}\), then for every bracket \(b\) in the sequence, if \(b \in O\) we push it onto the stack; if \(b \in C\), we pop from the stack and check if the popped bracket matches. The sequence is correctly nested if and only if the stack is empty at the end and every pop operation was valid.

inputFormat

The first line contains an integer T representing the number of test cases.

Each of the following T lines contains a string consisting of the characters (, ), [, ], {, and }. The string may be empty.

Input is read from standard input (stdin).

outputFormat

For each test case, print YES if the bracket sequence is correctly nested and NO otherwise. Each result should be printed on a new line.

Output is written to standard output (stdout).

## sample

5
()
([{}])
([]{)}
({[}])

YES
YES
NO
NO
YES

</p>