#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)
    {
     if (x[i]=='a')
	 {
	 x[i]=a[i];
	 break;
	 }
	 else if (x[i]=='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;
		       }
		       else if (x[i]=='c')
			       {
				if (a[i]=='2')//2
				    x[i]='2';
				    else 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;
					     }
					     else 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;
}