killjee has a string of parentheses containing '(',')','[',']','{','}' . Following are the rules to determine a valid parentheses string:

1. Empty string is valid.
2. (S), [S], {S} are valid strings where S is a valid parentheses string.
3. $AB$ is a valid parentheses string, where A and B both are themselves valid parentheses strings.

Example of some valid String:- ([]{}){}[] , ()(){}[] , ({[()]}) Example of some invalid String:- ({)}[] , ((}}} , ({)[]}

INPUT

First line of input contain a single integer t denoting number of testcases.

Each test contains a string s containing '(',')','[',']','{','}'

OUTPUT

For each test case, Output "YES" if string is valid else print "NO".

CONSTRAINTS

$1 \le t \le 100$

$1 \le |s| \le 2*10^{6}$