#include <iostream.h>
#include <fstream.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=0;j<lnp;j++)
   fin>>p[j];
 
  sw=1;
  lns=0;

  alg();

  memset(p,0,sizeof(p));
  memset(s,0,sizeof(s));

  fout<<((lnp==lns)&&sw)<<endl;
 }
 fin.close();
 fout.close();
 
return 0;
} 

void prima()
{
 if(lnp==1)
  sw=-1,lns=1;
 else
 {
  switch(p[0])
  {
   case '1': if(lnp==3){s[0]='1';s[1]='2';s[2]='A';lns=3;}
             else      {s[0]='1';s[1]='A';s[2]='3';s[3]='A';s[4]='C';lns=5;}break;
   case '2':           {s[0]='2';s[1]='B';lns=2;}break;
   case '3':           {s[0]='3';s[1]='B';s[2]='C';lns=3;}break;
  }    
 }
}

void alg()
{
 int i;

 prima();

 if(sw==-1)
 {
  sw=1;
  return;
 } 
 else
 {      
  
  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' ) { s[i]='1';s[i+1]='A';s[i+2]='3';s[i+3]='A';s[i+4]='C';lns+=4;}
                 else {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 {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  {s[i]='3';s[i+1]='B';s[i+2]='C';lns+=2;}break;
   }
 } //////////// for
}