#include<stdio.h>
int l,x[10009],n,i,j,ok;
int perla(int poz,int c)
{
	if(c==2)
	{ if(poz>l-4) return 0;
	  if(x[poz]==3) return 0;
	  if(x[poz]==2) return perla(poz+1,2);
	  if(x[poz+2]!=3) return 0;
	  return perla(poz+4,3);
	}
	if(x[poz]==2){if(poz==l)return 1;return 0;}
	if(x[poz]==1){ if(poz!=(l-2))return 0;if(x[poz+1]==2)return 1;return 0;}
	if(x[l-2]!=1)return 0;if(x[l-1]!=2)return 0;
	l=l-3; return perla(poz+1,2);
}
int main()
{    FILE *f,*g;
     f=fopen("perle.in","r");
     g=fopen("perle.out","w");
     fscanf(f,"%d",&n);
     for(i=1;i<=n;i++)
     {fscanf(f,"%d",&l);
      for(j=1;j<=l;j++)
      fscanf(f,"%d",&x[j]);
      if(l>=5)
	{ if(x[1]==3)ok=perla(1,3);
		else ok=perla(1,2);
	}
      else {if(l==1)ok=1;
	    if(l==2)ok=0;
	    if(l==4)ok=0;
	    if(l==3){if((x[1]==1)&&(x[2]==2))ok=1;
			else ok=0;}
	    }
      fprintf(g,"%d\n",ok);
     }
     fcloseall();
     return 0;
}