#include<stdio.h>
#include<string.h>

int i,j,n,l,ok,k,t;
char stiva[10010],c;
char b2[3]={2,'2','b'};
char b1[6]={5,'1','a','3','a','c'};
char c3[4]={3,'3','b','c'};
char c1[4]={3,'1','2','a'};


void copy(char a[])
{ 
	int n=int(a[0]);
	for(;n>1;--n) stiva[++k]=a[n];
}	

void solve()
{ int i=0;
	k=0;l=0;c=0;t=0,ok=0;;
	for( i=0;i<=40;++i) stiva[i]=0;
	scanf("%d",&l);
	
	if(l==1) {   scanf("%d",&t);
		         printf("1\n");
	             return ;
	         }
	if(l==3)
	{	 scanf("%d",&t);      
	     c=char(t+48);
		 if(c!='1') { ok=1;
     	            }
         scanf("%d",&t);      
	     c=char(t+48);
		 if(c!='2') { ok=1;
		            }
		 scanf("%d",&t);
		 
		 if(!ok) printf("1\n");
		 else printf("0\n");
         return ;
	}		 
     		 
    scanf("%d",&t);      
	  c=char(t+48);
	if(c=='1') copy(b1);
	else if(c=='2') copy(b2);
    else if(c=='3') copy(c3);
	
	for(i=2;i<=l;++i)  
	{ scanf("%d",&t);      
	  c=char(t+48);
	  
	  if(c==stiva[k]) --k;
	  else if(c=='1') 
	  {	if(stiva[k]=='a') --k;
	    else if(stiva[k]=='b') --k,copy(b1);
	    else if(stiva[k]=='c') --k,copy(c1);
        else {ok=1;
		     }
	  }
	  else if(c=='2')
	  { if(stiva[k]=='a'||stiva[k]=='c') --k;
	    else if(stiva[k]=='b') --k,copy(b2);
	    else { ok=1;
		     }
	  }
	  else if(c=='3')
	  { if(stiva[k]=='a') --k;
	    else if(stiva[k]=='c') --k,copy(c3);
	    else { ok=1;
		     }
	  }
	}
		       
    if(k==0&&!ok)printf("1\n");
	else printf("0\n");
}	

int main()
{ 
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;++i) solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}