#include <iostream.h>
#include <fstream.h>
ifstream fin("perle.in");
ofstream fout("perle.out");


char y[100],y1[100];
int i,n,ok;


void proc(int k, int lg)
{int i;

 if (!ok)
 {while (y[k]==y1[k] && k<=lg) k++;
  if (k==lg && lg==n) ok=1;
   else
    if(k<=lg && lg<=n)
    ///////////////////
     {if (n-k>=0 && y1[k]=='A') //1|2|3
      {y1[k]=y[k]; proc(k+1,lg);
      }
      if (n-k>=2 && y[k]=='1' && y[k+1]=='2' && y1[k]=='C') //12_
      {for (i=lg;i<=k;i++)
       y1[i+2]=y1[i];
       y1[k]='1';
       y1[k+1]='2';
       y1[k+2]='A';
       proc(k+1,lg+2);
       }
      if (n-k>=1 && y[k]=='2' && y1[k]=='B')//2_.....
      {for (i=lg;i<=k;i++)
       y1[i+1]=y1[i];
       y1[k]='2';
       y1[k+1]='B';
       proc(k+1,lg+1);
	}
      if (n-k>=4 && y[k]=='1' && y1[k]=='B')//1A3AC...
      {
      for (i=lg;i<=k;i++)
       y1[i+4]=y1[i];
       y1[k]='1';
       y1[k+1]='A';
       y1[k+2]='3';
       y1[k+3]='A';
       y1[k+4]='C';
       proc(k+1,lg+4);
       }
      if (n-k>=2 && y[k]=='3' && y1[k]=='C')//3BC..
      {for (i=lg;i<=k;i++)
       y1[i+2]=y1[i];
       y1[k]='3';
       y1[k+1]='B';
       y1[k+2]='C';
       proc(k+1,lg+2);
   }    }

 }
}




int main()
{int i,j,m;
fin>>m;
for (j=1;j<=m;j++)
{fin>>n;
for (i=1;i<=n;i++)
fin>>y[i];

ok=0;
if (n==1) //1|2|3
ok=1;
else
 if (n==3 && y[1]=='1' && y[2]=='2') //12_
  ok=1;
  else
   if (n>2 && y[1]=='2')//2_.....
    {y1[1]='B';
    proc(1,1);
    }
    else
      if (n>=5 && y[1]=='1')//1A3AC...
      {y1[1]='1';
       y1[2]='A';
       y1[3]='3';
       y1[4]='A';
       y1[5]='C';
       proc(1,5);
      }
       else
	if (n>=3 && y[1]=='3')//3BC..
	 {y1[1]='3';
	  y1[1]='B';
	  y1[1]='C';
	 proc(1,3);
	 }

fout<<ok<<endl;
}
return 0;
}