#include <fstream.h>   
#include <iostream.h>   
  
#define IN "perle.in"   
#define OUT "perle.out"   
#define DIM 10011   
  
ifstream fin(IN);   
ofstream fout(OUT);   
  
char s[DIM],p[DIM];   
int n,lnp,lns;   
int sw;   
  
void alg();   
void prima();   
  
int main()   
{   
 int i, j;   
    
 fin>>n;   
 for(i=1;i<=n;i++)   
 {   
  fin>>lnp;                   
  for(j=1;j<=lnp;j++)   
   fin>>p[j];   
  
  if(lnp==1)   
   fout<<1<<endl;   
  else   
  {    
   alg();   
  
   memset(p,0,sizeof(p));   
   memset(s,0,sizeof(s));   
  
   fout<< !( lnp<lns || !sw ) <<endl;   
  }    
 }   
 fin.close();   
 fout.close();   
  
return 0;   
}   
  
void prima()   
{   
    
  sw=0;   
  switch(p[1])   
  {   
   case '1': if(lnp==3){s[1]='1';s[2]='2';s[3]='A';lns=3;sw=1;}   
         else      {s[1]='1';s[2]='A';s[3]='3';s[4]='A';s[5]='C';lns=5;sw=1;}break;   
   case '2':           {s[1]='2';s[2]='B';lns=2;sw=1;}break;   
   case '3':           {s[1]='3';s[2]='B';s[3]='C';lns=3;sw=1;}break;   
  }   
  
}   
  
void alg()   
{   
 int i,j;   
  
 prima();   
  
  for(i=1,sw=1;(i<=lnp && lns<=lnp && sw); i++)   
   switch(p[i])   
   {   
    case '1': if(s[i]=='2' || s[i]=='3') sw=0;   
          else   
           if(s[i]=='1' || s[i]=='A') s[i]='1';   
           else   
        if(s[i]=='B' ) {for(j=lns;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';lns+=4;}   
         else {for(j=lns;j>i;j--)s[j+2]=s[j]; s[i]='1';s[i+1]='2';s[i+2]='A';lns+=2;}break;   
  
    case '2': if(s[i]=='1' || s[i]=='3') sw=0;   
          else   
           if(s[i]=='2' || s[i]=='A' || s[i]=='C') s[i]='2';   
           else {for(j=lns;j>i;j--)s[j+1]=s[j]; s[i]='2';s[i+1]='B';lns++;}break;   
  
    case '3': if(s[i]=='1' || s[i]=='2'|| s[i]=='B') sw=0;   
          else   
           if(s[i]=='3' || s[i]=='A' ) s[i]='3';   
           else  {for(j=lns;j>i;j--)s[j+2]=s[j]; s[i]='3';s[i+1]='B';s[i+2]='C';lns+=2;}break;   
   }   
  
}