1#include <iostream>
2#include <algorithm>
3#include <unordered_map>
4#include <stack>
5using namespace std;
6string isBalanced(string s){
7 stack <char> st;
8 for(auto c:s){
9 switch (c){
10 case '(':
11 case '{':
12 case '[':
13 st.push(c);
14 break;
15 case '}':
16 if(st.empty() || st.top()!='{' )
17 return "NO";
18 st.pop();
19 break;
20 case ']':
21 if(st.empty() || st.top()!='[')
22 return "NO";
23 st.pop();
24 break;
25 case ')':
26 if(st.empty() || st.top()!='(')
27 return "NO";
28 st.pop();
29 break;
30 default: break;
31 }
32 }
33 return st.empty() ? "YES":"NO";
34}
35
36int main(){
37 int t;
38 cin >> t;
39 for(int a0 = 0; a0 < t; a0++){
40 string s;
41 cin >> s;
42 cout << isBalanced(s) << endl;
43 }
44 return 0;
45}
46