If a is legal, (a), {a}, [a] are legal;
If a and b are both legal, ab is legal.

You are given a string S with length of n. Assume that Si(1 <= i <= n) is the i-th character of S. Your task is to find out whether there is a k(1 <= k <= n) that SkSk+1Sk+2…SnS1S2…Sk-1 is legal.

Input
There are several test cases. The first line contains an integer N. Then N test cases follows. In each test case, there is an only line that contains S. The length of S will not be larger than 1000. There are only (, ), {, }, [, ] in S.

Output
For each test case, output a single line “YES” (without quotation marks) if there is such a k, or “NO” (without quotation marks) otherwise.

Sample Input
3
}()[]{
}([)]{
()][

Sample Output
YES
NO
YES

! /usr/bin/env python

import string, sys

def exchange_str(str, i):
str1 = str[0:i]
str2 = str[i:]
return str2+str1

def is_legal(str):
if(len(str)==0):
return 1
if(len(str)==1):
return 0

if(str[0]=='('):
    i = string.find(str, ")")
    if(i==-1):
        return 0
    elif(i==len(str)-1):
        return is_legal(str[1:len(str)-1])
    else:
        return is_legal(str[0:i+1]) and is_legal(str[i+1:len(str)])
if(str[0]=='['):
    i = string.find(str, "]")
    if(i==-1):
        return 0
    elif(i==len(str)-1):
        return is_legal(str[1:len(str)-1])
    else:
        return is_legal(str[0:i+1]) and is_legal(str[i+1:len(str)])
if(str[0]=='{'):
    i = string.find(str, "}")
    if(i==-1):
        return 0
    elif(i==len(str)-1):
        return is_legal(str[1:len(str)-1])
    else:
        return is_legal(str[0:i+1]) and is_legal(str[i+1:len(str)])

n = string.atoi(sys.stdin.readline())
while(n!=0):
str = sys.stdin.readline()
str = str[0:len(str)-1]
tmp = “”
legal = 0;
for i in range(0, len(str)):
tmp = exchange_str(str, i)

    #print "==>"+tmp+"n"
    if(is_legal(tmp)):
        legal = 1
        break
if(legal==1):
    print "YES"
else:
    print "NO"
n-=1