#include<stdio.h>
int n,i,j,l,l1,l2,ok,x[10001],y[10001],p,k;
int prel();
int prel14();
int prel15();
int prel24();
int prel25();
int prel34();
int prel35();
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==1) ok=2;
    else ok=1;l1=l;l2=1;p=1;
    if(x[1]==1){if(l>=4)y[1]=4;else y[1]=5;}
    if(x[1]==2)y[1]=4;if(x[1]==3)y[2]=5;
    while(ok==1)
    ok=prel();
    if(ok==2)fprintf(g,"1\n");
    else fprintf(g,"0\n");
  }
  fcloseall();
  return 0;
}
int prel()
{
	if(x[p]==1){ if(y[1]==4) return prel14();return prel15();}
	if(x[p]==2){ if(y[1]==4) return prel24();return prel25();}
		     if(y[1]==4) return prel34();return prel35();
}
int prel14()
{
	p=p+2;l1=l1-2;if(l1<=0) return 0; if(x[p]!=3) return 0;
	p=p+2;l1=l1-2;if(l1<=0) return 0; y[1]=5; return 1;
}
int prel15()
{
	p=p+1;l1=l1-1;if(l1<=0) return 0; if(x[p]!=2) return 0;
	p=p+2;l1=l1-2;if(l1<0) return 0;
	l2=l2-1;if(l2==0) {if(l1==0) return 2;else return 0;}
	if(l1==0) return 0;
	for(k=1;k<=l2;k++) y[k]=y[k+1]; return 1;
}
int prel24()
{
	p=p+1;l1=l1-1; if(l1<=0) return 0; return 1;
}
int prel25()
{
	p=p+1;l1=l1-1;l2=l2-1;
	if(l2==0){if(l1==0) return 2;return 0;}
	if(l1<=0) return 0;
	for(k=1;k<=l2;k++) y[k]=y[k+1]; return 1;
}
int prel34()
{
	return 0;
}
int prel35()
{
	p=p+1;l1=l1-1;l2=l2+2;
	if(l1<l2) return 0;
	for(k=l2;k>=2;k--) y[k]=y[k-1];y[1]=4;return 1;
}