A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

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

using namespace std;

string isBalanced(string s) {
    // Mapping of closing brackets to their corresponding opening brackets
    unordered_map<char, char> bracketMap = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };
    
    stack<char> stk;
    
    for (char ch : s) {
        // If it's an opening bracket, push it onto the stack
        if (bracketMap.find(ch) == bracketMap.end()) {
            stk.push(ch);
        } 
        // If it's a closing bracket
        else {
            // Check if the stack is empty or the top of the stack doesn't match
            if (stk.empty() || stk.top() != bracketMap[ch]) {
                return "NO";
            }
            // Pop the matching opening bracket
            stk.pop();
        }
    }
    
    // If the stack is empty, all brackets matched correctly
    return stk.empty() ? "YES" : "NO";
}

int main() {
    int n;
    cin >> n; // Read the number of strings
    cin.ignore(); // Ignore the newline after the number input

    for (int i = 0; i < n; ++i) {
        string s;
        getline(cin, s); // Read each bracket string
        cout << isBalanced(s) << endl; // Output YES or NO
    }
    
    return 0;
}