#include<stdio.h>
#define N 10005
int a=4,b=5,c=6,x[N],y[N],n,lg,j1,j2,ok,k,i;

void determinStart()
{if(x[1]==1)
     if(lg==1) 
             y[1]=a;
     else 
             if(lg==3&&x[2]==2) 
                    y[1]=c;
             else 
                    if(lg>=5) 
                           y[1]=b;
                    else 
                           ok=0;
else
    if(x[1]==2)
             if(lg==1) 
                    y[1]=a;
             else 
                    if(lg>=2) 
                           y[1]=b;
                    else 
                           ok=0;
    else
             if(x[1]==3)
                    if(lg==1) 
                           y[1]=a;
                    else 
                           if(lg>=3) 
                                    y[1]=c;
                           else 
                                    ok=false;}

void inserez3BC()
{int j;
j2+=2;
for(j=j2-1;j>=j1+2;j--) 
      y[j]=y[j-2];
y[j1]=3,y[j1+1]=b,y[j1+2]=c;}

void inserez12A()
{int j;
j2+=2;
for(j=j2-1;j>=j1+2;j--) 
       y[j]=y[j-2];
y[j1]=1,y[j1+1]=2,y[j1+2]=a;}

void inserez2B()
{int j;
j2++;
for(j=j2-1;j>=j1+1;j--) 
      y[j]=y[j-1];
y[j1]=2,y[j1+1]=b;}

void inserez1A3AC()
{int j;
j2+=4;
for(j=j2-1;j>=j1+4;j--) 
      y[j]=y[j-4];
y[j1]=1,y[j1+1]=a,y[j1+2]=3;
y[j1+3]=a,y[j1+4]=c;}

void cautNeterminal()
{while(j1<j2&&y[j1]<a&&ok)
     {if(y[j1]!=x[j1]) 
           ok=false;
     j1++;}}

void schimbNeterminal()
{if(y[j1]==a) 
       y[j1]=x[j1++]; 
else
       if(y[j1]==b)
              if(x[j1]==1) 
                      inserez1A3AC();
              else 
                      if(x[j1]==2) 
                              inserez2B();
                      else 
                              ok=false;
       else
              if(x[j1]==1) 
                      inserez12A();
              else 
                      if(x[j1]==2) 
                              y[j1++]=2;
                      else 
                              inserez3BC();}

int main()
{FILE *f=fopen("perle.in","r"),*g=fopen("perle.out","w");
fscanf(f,"%d",&n);
while(n--)
     {fscanf(f,"%d",&lg);
     for(k=1;k<=lg;k++)
            fscanf(f,"%d",&x[k]);
     ok=1;
     determinStart();
     if(!ok)
            {fprintf(g,"0\n");
            continue;}
     j1=1,j2=2;
     while(ok&&j1<=lg)
            {cautNeterminal();
            if(ok)
                  schimbNeterminal();
            if(j2>lg+1)
                  ok=0;}
     fprintf(g,"%d\n",ok);}
return 0;}