/*
#include <iostream>
#include <stdio.h>
#include <map>
#include <string.h>
using namespace std;
class tree
{
public:
int arr[2]= {0,0};
int cnt = 0;
char main_ = 0;
};
tree t[500];
void f(int n)
{
int i;
if(t[n].main_ == 0)
{
return;
}
f(t[n].arr[0]);
printf("%c",t[n].main_);
f(t[n].arr[1]);
}
int main()
{
int test;
int n;
int i,j;
int x;
char str[100];
int num;
for(test = 1; test <= 10; test++)
{
scanf("%d ",&n);
for(i = 0; i < n; i++)
{
num = 0;
scanf("%d ",&x);
gets(str);
//printf("a %d %s\n",strlen(str),str);
t[x].main_ = str[0];
if(strlen(str)!= 1)
{
///
for(j = 2; str[j]<='9'&&str[j]>='0'; j++)
{
num=(num*10)+(str[j]-'0');
// printf("a");
}
t[x].arr[0] = num;
if(strlen(str)!=j)
{
num = 0;
for(j++;str[j]<='9'&&str[j]>='0'; j++)
{
num=(num*10)+(str[j]-'0');
}
t[x].arr[1] = num;
}
else
{
t[x].arr[1] = 0;
}
}
else
{
t[x].arr[0] = 0;
t[x].arr[1] = 0;
}
}
printf("#%d ",test);
f(1);
puts("");
}
}
*/
/*
#include <iostream>
#include <stdio.h>
#include <map>
#include <string.h>
#include <stdlib.h>
using namespace std;
struct grape
{
int arr[3];
int cnt = 0;
};
grape fruit[101];
bool visted[101];
bool f(int n)
{
// printf("%d,",n);
bool a;
if(n == 99)
{
return true;
}
if(n>=100||visted[n])
{
return false;
}
visted[n] = true;
a = f(fruit[n].arr[0]);
if(a)
{
return a;
}
a = f(fruit[n].arr[1]);
return a;
}
int main()
{
int n,m;
int test;
int x;
int i;
for(test = 1; test <= 10; test++)
{
memset(visted,false,sizeof(visted));
for(i = 0; i < 100; i++)
{
fruit[i].cnt = 0;
memset(fruit[i].arr,100,sizeof(fruit[i].arr));
}
scanf("%d %d",&test,&x);
for(i = 0;i < x;i++)
{
scanf("%d %d",&n,&m);
fruit[n].arr[fruit[n].cnt] = m;
fruit[n].cnt++;
}
printf("#%d %d\n",test,f(0));
}
}
*/
#include <iostream>
#include <stdio.h>
#include <stack>
#include <string.h>
#include <stdlib.h>
using namespace std;
bool open(char a)
{
if(a=='<'||a=='('||a=='{'||a=='[')
{
return 1;
}
return 0;
}
bool close(char a)
{
if(a=='>'||a==')'||a=='}'||a==']')
{
return 1;
}
return 0;
}
bool match(char a,char b)
{
if(a=='<'&&b=='>')
{
return 1;
}
if(a=='('&&b==')')
{
return 1;
}
if(a=='{'&&b=='}')
{
return 1;
}
if(a=='['&&b==']')
{
return 1;
}
return 0;
}
int main()
{
stack<char> st;
char temp[10000];
int n,i;
int test;
bool answer;
for(test = 1;test <= 10;test++)
{
answer = 1;
scanf("%d ",&n);
scanf("%s",temp);
for(i = 0;i < n;i++)
{
//printf("%c",temp);
if(close(temp[i])&&answer)
{
if(st.empty())
{
answer = false;
}
else if(match(st.top(),temp[i]))
{
st.pop();
}
else
{
answer = false;
}
}
if(open(temp[i]))
{
st.push(temp[i]);
}
}
answer = st.empty()&&answer;
printf("#%d %d\n",test,answer);
}
}