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


void determinStart(){
//determina cu ce poate incepe (perla de inceput)
switch(x[1]){
case 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;
	}
	break;
	}
case 2:{if(lg==1){y[1]=a;ok=1;}
	else if(lg>=2){y[1]=b;ok=1;}
	else ok=0;
	break;
	}
case 3:{if(lg==1){y[1]=a;ok=1;}
	else if(lg>=3){y[1]=c;ok=1;}
	else ok=0;
	break;
	}
}
}

void inserez1A3AC(){
int j;
j2+=4;
//muta tot mai spre dreapta, sa faci loc transformarii
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 inserez2B(){
int j;
j2++;
for(j=j2-1;j>=j1+1;j--)y[j]=y[j-1];
y[j1+0]=2;
y[j1+1]=b;
}

void inserez12A(){
int j;
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 inserez3BC(){
int j;
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 cautNeterminal(){
while((j1<j2)&&(y[j1]<a)&& ok){
if(y[j1]!=x[j1])ok=0;
j1++;
}
}

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

/*void afisare(){
int j;
for(j=1;j<j2;j++)cout<<x[j]<<" ";
} */

int main(){
int k,i;
FILE *fin,*fout;
fin=fopen("perle.in","r");
fout=fopen("perle.out","w");
//clrscr();
fscanf(fin,"%d",&n);
for(k=1;k<=n;k++){
  fscanf(fin,"%d",&lg);
  for(i=1;i<=lg;i++){fscanf(fin,"%d",&x[i]);}
  ok=1;
  determinStart();
  if(!ok){fprintf(fout,"0\n");continue;}
  //daca totusi e ok
  j1=1;
  j2=2;//prima poz libera
  while(ok&&(j1<=lg)){
  cautNeterminal();
  if(ok)schimbNeterminal();
  if(j2>lg+1)ok=0;
  }
fprintf(fout,"%d\n",ok); //afisare();cout<<endl;
}
return 0;
}