Balanced Brackets

Given n strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, print YES on a new line; otherwise, print NO on a new line.

Input Format

The first line contains a single integer n denoting the number of strings.
Each line  of the  subsequent lines consists of a single string s denoting a sequence of brackets.

Output Format

For each string, print whether or not the string of brackets is balanced on a new line. If the brackets are balanced, print YES; otherwise, print NO.

t = { ')': '(', ']':'[', '}':'{' }
for i in range(int(input())):
    s = []
    for x in input():
        if s and t.get(x) == s[-1]:
            s.pop()
        else:
            s.append(x)
    print("NO" if s else "YES")