#include <stdio.h>


int v[20000],k,l,n,i,j;

int functie()
 {
  if (l==1) return 1;
  if ((l==3) && (v[1]==1) && (v[2]==2))  return 1;
  if (l>4) {if ((v[1]==1) || (v[1]==2))
		 {k=1;
		  while (v[k]==2) k++;
		  if (v[k]!=1) return 0;
		  k=k+2;
		  if (v[k]!=3) return 0;
		  k=k+2;
		  if ((v[l-1]==2) && (v[l-2]==1)) l=l-3;
			       else
			if (v[l]==2) l=l-1;
				else return 0;
		  while (k<l)
		    {if (v[k]!=3) return 0;
		     k++;
		     while (v[k]==2) k++;
		     if (v[k]!=1) return 0;
		     k=k+2;
		     if (v[k]!=3) return 0;
		     k=k+2;
		     if ((v[k]==1) && (v[k+1]==2)) k=k+3;
			      else if (v[k]==2) k++;
				  else return 0;
		     }
		  return 1;
		  }
	    if (v[1]==3)
		  {k=1;
		   if ((v[l-1]==2) && (v[l-2]==1)) l=l-3;
			    else
			  if (v[l]==2) l=l-1;
			       else return 0;
		   while (k<l)
		     {if (v[k]!=3) return 0;
		      k++;
		      while (v[k]==2) k++;
		      if (v[k]!=1) return 0;
		      k=k+2;
		      if (v[k]!=3) return 0;
		      k=k+2;
		      }
		   return 1;
		   }
	  }
return 0;
 }


int main()
{FILE *fin,*fout;


fin=fopen("perle.in","r");
fout=fopen("perle.out","w");
fscanf(fin,"%d",&n);

for (i=1;i<=n;i++)
  {fscanf(fin,"%d",&l);
   for (j=1;j<=l;j++)
     fscanf(fin,"%d",&v[j]);
   fprintf(fout,"%d",functie());
   fprintf(fout,"\n");
   }

fclose(fin);
fclose(fout);

return 0;
}