#include <stdio.h>

#define FIN "perle.in"
#define FOUT "perle.out"
#define N_MAX 11000


int n,i,ii,j,nr,ok,y,T;
char a[N_MAX];
char x[N_MAX];




int solve(int n)
{
for(i=1;i<=n;i++)
   switch(x[i]){
   case 'a':
      {
      x[i]=a[i];
      break;
      }
      case 'b':
	      {
	      if (a[i]=='2') //2b
		{
		for(ii=n+1;ii>=i+2;ii--)
		   x[ii]=x[ii-1];
		   x[i]='2';
		   x[i+1]='b';
		   n++;
		 }
		 if (a[i]=='1')//1a3ac
		    {
		    for(ii=n+4;ii>=i+5;ii--)
		       x[ii]=x[ii-4];
		       x[i]='1';
		       x[i+1]='a';
		       x[i+2]='3';
		       x[i+3]='a';
		       x[i+4]='c';
		       n+=4;
		    }
	  break;
	 }
	  case 'c':
	   {
	    if(a[i]=='2') //2
	       x[i]='2';
	     if(a[i]=='3')//3bc
	       {
		for(ii=n+2;ii>=i+3;ii--)
		   x[ii]=x[ii-2];
		   x[i]='3';
		   x[i+1]='b';
		   x[i+2]='c';
		   n+=2;
	       }
	  if (a[i]=='1')//12a
	    {
	    for(ii=n+2;ii>=i+3;ii--)
	       x[ii]=x[ii-2];
	       x[i]='1';
	       x[i+1]='2';
	       x[i+2]='a';
	       n+=2;
	    }
	  break;
	 }
}
if(n>y) return 0;
if(n==y)
  {
  nr=0;
  for(ii=1;ii<=y;++ii)
     if(a[ii]!=x[ii])
       {
       nr=1;
       break;
       }
   if (!nr)
   return 1;
  }
return 0;
}


int main()
{

freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%d", &T);

while (T)
      {
       scanf("%d", &y);
       for (j=1;j<=y;++j)
	   scanf("%d", &a[j]);
		ok=0;
		 x[1]='a';
		 if (solve(1)==1)
		     {
		      printf("1\n");
		      ok=1;
		      }
		 x[1]='b';
		 if (solve(1)==1 && ok==0)
		     {
		      printf("1\n");
		      ok=1;
		      }
		 x[1]='c';
		 if (solve(1)==1 && ok==0)
		     {
		      printf("1\n");
		      ok=1;
		      }
		 if (ok==0)
		     printf("0\n");
	--T;
}
return 0;
}