#include<stdio.h>
#include<string.h>
long n,a[10005],t,tt,i,da;
/*long rec(long poz)
{long ok1,ok2,ok3,i;
 if(x[poz]==0) return 0;
 if(poz>n+1)return 0;
 if(x[poz]<=3&&a[poz]!=x[poz])return 0;
 if(poz==n)if(x[poz]<=4)return 1;
                   else return 0;
 if(x[poz]<4)return rec(poz+1);
 if(x[poz]==4)
 {x[poz]=a[poz];
  ok1=rec(poz+1);
  x[poz]=4;
  return ok1;}
 if(x[poz]==5)
 {if(x[n])return 0;
  ok1=0;
  if(a[poz]==2)
    {for(i=n;i>=poz+2;--i)
        x[i]=x[i-1];
     x[poz]=2;
     x[poz+1]=5;
     ok1=rec(poz+1);
     for(i=poz;i<n;++i)
        x[i]=x[i+1],x[i+1]=0;
     x[poz]=5;}
  ok2=0;
  if(!x[n]&&!x[n-1]&&!x[n-2]&&!x[n-3]&&a[poz]==1&&a[poz+2]==3)
    {for(i=n;i>=poz+5;--i)
        x[i]=x[i-4];
     x[poz+4]=6;
     ok2=rec(poz+4);
     for(i=poz;i<n-3;++i)
        x[i]=x[i+4],x[i+4]=0;
     x[poz]=5;}
   return(ok1||ok2);}
 if(x[poz]==6)
   {ok1=0;
    if(a[poz]==2)ok1=rec(poz+1);
    ok2=0;
    ok3=0;
    if(!x[n]&&!x[n-1])
    {
     if(a[poz]==3)
       {for(i=n;i>=poz+3;--i)
           x[i]=x[i-2];
        x[poz+1]=5;
        x[poz+2]=6;
        ok2=rec(poz+1);
        for(i=poz;i<n-2;++i)
           x[i]=x[i+2],x[i+2]=0;
        x[poz]=6;}
     if(a[poz]==1&&a[poz+1]==2)
       {for(i=n;i>=poz+3;--i)
           x[i]=x[i-2];
        x[poz+2]=4;
        ok3=rec(poz+2);
        for(i=poz;i<n-2;++i)
           x[i]=x[i+2],x[i+2]=0;}
        x[poz]=6;}
    return (ok1||ok2||ok3);}
 return 0;
}  */
long B(long poz);
long C(long poz);
int main()
{
 freopen("perle.in","r",stdin);
 freopen("perle.out","w",stdout);
 scanf("%ld",&t);
 for(tt=1;tt<=t;++tt)
   {scanf("%ld",&n);
    for(i=1;i<=n;++i)
       scanf("%ld",&a[i]);
    if(n==1){printf("1\n");continue;}
    da=B(1);
    if(da){printf("1\n");continue;}
    da=C(1);
    if(da){printf("1\n");continue;}
    printf("0\n");}
 return 0;
}
long B(long poz)
{if(n<poz)return 0;
if(a[poz]==2)return B(poz+1);
if(a[poz]==1&&a[poz+2]==3)return C(poz+4);
return 0;}
long C(long poz)
{if(n<poz)return 0;
 if(a[poz]==2)
   return poz;
 if(a[poz]==1&&a[poz+1]==2)
   return poz+2;
 if(a[poz]==3)
   {poz=B(poz+1);
    if(poz)return C(poz+1);}
return 0;}