#include <stdio.h>

int a=4, b=5, c=6;
int x[10001],y[10001];
int n,lg,j1,j2,ok;

void start(){
     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=0;
         }
}

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

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

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

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

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

void changewadafac(){
     if(y[j1]==a){
         y[j1]=x[j1];
         j1++;}
     else
         if(y[j1]==b){
             if(x[j1]==1) insert4();
             else if(x[j1]==2) insert3();
             else ok=0;
         }
     else{
         if(x[j1]==1) insert2();
         else if(x[j1]==2) {y[j1]=2; j1++;}
     else 
        insert1();
     }
}

int main(){
    int k,i;
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    scanf("%d",&n);
    for(k=1;k<=n;k++){
        scanf("%d",&lg);
        for(i=1;i<=lg;i++)
            scanf("%d",&x[i]);
        ok=1;
        start();
        if(ok==0){
           printf("0\n");
           continue;
        }
        j1=1;
        j2=2;
        while((ok)&&(j1<=lg)){
            cautare();
            if(ok) changewadafac();
            if(j2>lg+1) ok=0;
        }
        if(ok) printf("1\n");
        else printf("0\n");
    }
    fclose(stdout);
}