#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;

 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' ) { 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;
   }

}