#include<stdio.h>

int v[10001];
int posibil_a(int x,int y);
int posibil_b(int x,int y);
int posibil_c(int x,int y);

int posibil_a(int x,int y)
{
 if(y==x) return 1;
  else return 0;
}

int posibil_b(int x,int y)
{
 if(x>=y) return 0;
 if(v[x]==2)
  return posibil_b(x+1,y);
   else if(v[x]==1)
    {
     if(v[x+2]!=3) return 0;
     return posibil_c(x+4,y);
    }else return 0;
}

int posibil_c(int x,int y)
{
 if(x>y) return 0;
 if(v[x]==2)
  {
   if(x==y) return 1;
    else return 0;
  }
 if(v[x]==1)
  {
   if(v[x+1]!=2 || (y!=x+2)) return 0;
    return 1;
  }
 //v[x] mai poate fi 3 si avem 3BC
 x++;
 while(v[x]==2 && x<=y) x++;
 //ar trebui sa mai avem 1A3ACC
 if(v[x]!=1 || v[x+2]!=3) return 0;
 x+=4;
 if(x>y) return 0;
 //secventa ramasa ar trebui sa fie CC
 if(v[x]==2) return posibil_c(x+1,y);
 if(v[x]==1)
  {
   if(v[x+1]!=2) return 0;
    else return posibil_c(x+3,y);
  }
 //ar trebui sa ramana 3BCC
 if(y-x>160)//secventa e prea mare
  return 1;//nu mai e timp
 int ok=0,i;
 for(i=x+1;i<=y-1;i++)
  ok=ok||(posibil_c(x,i)&&posibil_c(i+1,y));
 return ok;
}

int posibil(void)
{
 if(posibil_a(1,v[0])) return 1;
 if(posibil_b(1,v[0])) return 1;
 if(posibil_c(1,v[0])) return 1;
 return 0;
}


int main()
{
 FILE *fin=fopen("perle.in","r"),*fout=fopen("perle.out","w");
 int n,i,j;
 fscanf(fin,"%d\n",&n);
 for(i=1;i<=n;i++)
  {
   fscanf(fin,"%d",&v[0]);
   for(j=1;j<=v[0];++j)
    fscanf(fin,"%d",&v[j]);
   fprintf(fout,"%d\n",posibil());
  }
 fclose(fin);
 fclose(fout);
 return 0;
}