#include <bits/stdc++.h>

using namespace std;

string isBalanced(string expr) {
        stack<int> s;

        vector<int> cptOpen(3,0);
        vector<int> cptClosed(3,0);

        for(int i=0; i < expr.length() ; i++){
            if(expr[i]=='('){
                cptOpen[0]++;
            }
            if(expr[i]==')'){
                cptClosed[0]++;
            }

            if(expr[i]=='['){
                cptOpen[1]++;
            }
            if(expr[i]==']'){
                cptClosed[1]++;
            }

            if(expr[i]=='{'){
                cptOpen[2]++;
            }
            if(expr[i]=='}'){
                cptClosed[2]++;
            }
        }

        for(int i=0;i<3;i++){
            if(cptOpen[i]!=cptClosed[i]){
                return "NO";
            }
        }

        for(int i=0;i<expr.length();i++){
            if(expr[i]=='('){
                s.push(1);
            }
            if(expr[i]==')'){
                if(s.empty() || s.top()!=1){
                    return "NO";
                }
                s.pop();
            }

            if(expr[i]=='['){
                s.push(2);
            }

            if(expr[i]==']'){
                if(s.empty() || s.top()!=2){
                    return "NO";
            }
                s.pop();
            }

            if(expr[i]=='{'){
                s.push(3);
            }
            if(expr[i]=='}'){
                if(s.empty() || s.top()!=3){
                    return "NO";
                }
                s.pop();
            }
        }
        return "YES";
    }

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