#include<stdio.h>
int main()
{
 char s[10001], p[10001];
 int k,i, j, ls, lp, n,ok;
 freopen("perle.in", "rt", stdin);
 freopen("perle.out", "wt", stdout);
 scanf("%d", &n);
 for(k=0;k<n;k++)
 {
  scanf("%d ", &lp);
   for(i=1; i<=lp;i++)
     scanf("%c ", &p[i]);
  if(lp==1) printf("1\n");
  else
  {
  switch(p[1])
  {
   case '1': if(lp==3) {s[1]='1';
   		      s[2]='2';
		      s[3]='A';
                      ls=3;
                     }
              else {s[1]='1';
           	 s[2]='A';
                 s[3]='3';
                 s[4]='A';
                 s[5]='C';
                 ls=5;
                }
             break;
   case '2': s[1]='2';
   	     s[2]='B';
	     ls=2;
	     break;
   case '3': s[1]='3';
   	     s[2]='B';
	     s[3]='C';
	     ls=3;
	     break;
  }
  for(i=2,ok=1;i<=lp && ls<=lp && ok; i++)
   switch(p[i])
  {
   case '1': if(s[i]=='2' || s[i]=='3') ok=0;
   	       else if(s[i]=='1' || s[i]=='A') s[i]='1';
                     else if(s[i]=='B' ) { for(j=ls;j>i;j--)
                     				s[j+4]=s[j];
                                           s[i]='1';
                                    	   s[i+1]='A';
                                           s[i+2]='3';
                                           s[i+3]='A';
                                           s[i+4]='C';
                                           ls+=4;
                                          }
                            else { for(j=ls;j>i;j--)
                     				s[j+2]=s[j];
                                           s[i]='1';
                                    	   s[i+1]='2';
                                           s[i+2]='A';
                                           ls+=2;
                                          }
             break;
   case '2': if(s[i]=='1' || s[i]=='3') ok=0;
   	       else if(s[i]=='2' || s[i]=='A' || s[i]=='C') s[i]='2';
                     else  { for(j=ls;j>i;j--)
                     				s[j+1]=s[j];
                                           s[i]='2';
                                           s[i+1]='B';
                                           ls++;
                                          }
	     break;
   case '3': if(s[i]=='1' || s[i]=='2'|| s[i]=='B') ok=0;
   	       else if(s[i]=='3' || s[i]=='A' ) s[i]='3';
                     else  { for(j=ls;j>i;j--)
                     				s[j+2]=s[j];
                                           s[i+1]='B';
                                           s[i]='3';
                                           s[i+2]='C';
                                           ls+=2;
                                          }
	     break;
  }
  if(!ok || ls>lp)  printf("0\n");
  else printf("1\n");
 }

 scanf("\n");
 }
 printf("\n");
 return 0;
}