#include <stack>
#include <string>
#include <iostream>

using namespace std;

string isBalanced(string s) {
    stack<char> st;  
    
    for (auto c: s) {
        switch (c) {
            case '{':
            case '(':
            case '[':
                st.push(c);
                break;
            case '}':
                if (st.empty() || (st.top() != '{')) {
                    return "NO";
                }
                st.pop();
                break;
            case ')':
                if (st.empty() || (st.top() != '(')) {
                    return "NO";
                }
                st.pop();
                break;
            case ']':
                if (st.empty() || (st.top() != '[')) {
                    return "NO";
                }
                st.pop();
                break;
        }
    }
    
    return st.empty() ? "YES" : "NO";
}


int main(){
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        string s;
        cin >> s;
        cout << isBalanced(s) << endl;
    }
    return 0;
}

let n = -1;
	while (s.length != n) {
		n = s.length;
		s = s.replace('()', '');
		s = s.replace('[]', '');
		s = s.replace('{}', '');
	}
	if (s.length == 0)
		return "YES"
	else 
		return "NO"

lefts = '{[('
rights = '}])'
closes = { a:b for a,b in zip(rights,lefts)}

def valid(s):
    stack = []
    for c in s:
        if c in lefts:
            stack.append(c)
        elif c in rights:
            if not stack or stack.pop() != closes[c]:
                return False
    return not stack  # stack must be empty at the end

t = int(raw_input().strip())
for a0 in xrange(t):    
    s = raw_input().strip()    
    if valid(s):
        print 'YES'
    else:
        print 'NO'

public boolean isValid(String s){
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
               stack.push('}');
               else if(c=='[')
               stack.push(']');
               else if(stack.isEmpty()||stack.pop()!=c)
               return false;
        }
               return stack.isEmpty();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            String s = in.next();
                System.out.println(isValid(s) ? "YES":"NO");
        }
    }

def isBalanced(s):
    restart=True
    while restart:
        if '{}' in s:
            s=s.replace('{}','')
        elif '()' in s:
            s=s.replace('()','')
        elif '[]' in s:
            s=s.replace('[]','')
        else:
            restart=False
    return 'YES' if len(s)==0 else 'NO'