#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
bool ArePair(char opening, char closing)
{
if(opening == '(' && closing == ')') return true;
else if(opening == '{' && closing == '}') return true;
else if(opening == '[' && closing == ']') return true;
return false;
}
bool AreParenthesesBalanced(std::string exp)
{
std::stack<char> s;
for(int i = 0; i < exp.length(); i++)
{
if(s.empty())
s.push(exp[i]);
else
{
if(ArePair(s.top(), exp[i]))
s.pop();
else
s.push(exp[i]);
}
}
return s.empty() ? true : false;
}
int main() {
std::string exp;
int ntests;
std::cin >> ntests;
while(ntests--){
std::cin >> exp;
std::cout << (AreParenthesesBalanced(exp) ? "YES" : "NO") << std::endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c3RhY2s+Cgpib29sIEFyZVBhaXIoY2hhciBvcGVuaW5nLCBjaGFyIGNsb3NpbmcpCnsKICAgIGlmKG9wZW5pbmcgPT0gJygnICYmIGNsb3NpbmcgPT0gJyknKSByZXR1cm4gdHJ1ZTsKICAgIGVsc2UgaWYob3BlbmluZyA9PSAneycgJiYgY2xvc2luZyA9PSAnfScpIHJldHVybiB0cnVlOwogICAgZWxzZSBpZihvcGVuaW5nID09ICdbJyAmJiBjbG9zaW5nID09ICddJykgcmV0dXJuIHRydWU7CiAgICByZXR1cm4gZmFsc2U7Cn0KCmJvb2wgQXJlUGFyZW50aGVzZXNCYWxhbmNlZChzdGQ6OnN0cmluZyBleHApCnsKICAgIHN0ZDo6c3RhY2s8Y2hhcj4gczsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBleHAubGVuZ3RoKCk7IGkrKykKICAgIHsKICAgICAgICBpZihzLmVtcHR5KCkpCiAgICAgICAgICAgIHMucHVzaChleHBbaV0pOwogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGlmKEFyZVBhaXIocy50b3AoKSwgZXhwW2ldKSkKICAgICAgICAgICAgICAgIHMucG9wKCk7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHMucHVzaChleHBbaV0pOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBzLmVtcHR5KCkgPyB0cnVlIDogZmFsc2U7Cn0KCmludCBtYWluKCkgewogICAgc3RkOjpzdHJpbmcgZXhwOwogICAgaW50IG50ZXN0czsKCgogICAgc3RkOjpjaW4gPj4gbnRlc3RzOwogICAgd2hpbGUobnRlc3RzLS0pewogICAgICAgIHN0ZDo6Y2luID4+IGV4cDsKICAgICAgICBzdGQ6OmNvdXQgPDwgKEFyZVBhcmVudGhlc2VzQmFsYW5jZWQoZXhwKSA/ICJZRVMiIDogIk5PIikgPDwgc3RkOjplbmRsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=