//https://practice.geeksforgeeks.org/problems/parenthesis-checker2744/1#
//pass all test cases but in submission it gets segmentation fault
//1 ≤ length of string ≤ 32000
#include <bits/stdc++.h>
using namespace std;
class solution{
public:
bool ispar(string x)
{
stack s;
s.push(x[0]);
for(int i=1;i<x.length();i++)
{
if(x[i]==’)’ && s.top()==’(’)
s.pop();
else if(x[i]=='}' && s.top()=='{')
s.pop();
else if(x[i]==']' && s.top()=='[')
s.pop();
else
s.push(x[i]);
}
if(s.empty())
return true;
else
return false;
}
};
int main()
{
int t;
string a;
cin>>t;
while(t–)
{
cin>>a;
solution obj;
if(obj.ispar(a))
cout<<“balanced”<<endl;
else
cout<<“not balanced”<<endl;
}
}