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

int procesB(char *s);
int procesC(char *s);
int t=0;
char *u;

int procesB(char *s)
{

       while(*s=='2') {s++;t++;}
	
	if(*s!='1') return 0;
	else
	{
		s++;
		t++;
		if(*s=='\0') return 0;
		else{
		s++;
		t++;
		if(*s!='3') return 0;
		else 
		{
			s++;
			t++;
			if(*s=='\0') return 0;
			else
			{
            		s++;
			t++; 
                        if(*s=='\0') return 0;
			else
			return procesC(s);
		}
	}
}

}
	}


int procesC(char *s)
{
	if(*s=='2') {t++;return 1;}
	else if(*s=='3')
	{
		s++;
		t++;
		if(procesB(s)==1)
		{s=u+t;return procesC(s);}
		else return 0;
	}

   else if(*s=='1')
   {
	   s++;
	   t++;		
	   if(*s!='2') return 0;
	   else
	   {   s++;
	       t++;	
	       if(*s=='\0') return 0;
		   else
		   {
		   s++;
		   t++;	
		   return 1;
	   	   }
           }
   }
    

}

       int main()
{
	char s[10001],*p,tip;
	int rez=0,n,i,lungime,j,nr;
	FILE *f=fopen("perle.in","r");
        FILE *g=fopen("perle.out","w");
	fscanf(f,"%i",&n);

        u=(char *) calloc(1,sizeof(char));
	
        
        for(i=0;i<n;i++)
        {

	fscanf(f,"%i",&lungime);
	//memset(s,0,10001);
	
	
        for(j=0;j<lungime;j++)
	{
        fscanf(f,"%i",&nr);
	s[j]=nr+'0';
	}
	s[lungime]='\0';
	p=s;
	//memset(u,0,1);
	u=&s[0];
	t=0;
	
	
	
	

        if(*(p+1)=='\0' && (*p=='1' || *p=='2' || *p=='3')) fprintf(g,"%c\n",'1');
	else
	{

	if(*p=='2' || (*p=='1' && *(p+3)!='\0')) tip='B';
	else if(*p=='3' || (*p=='1' && *(p+1)=='2' && *(p+3)=='\0')) tip='C';


	if(tip=='B')
	rez=procesB(p);
	else if(tip=='C')
	rez=procesC(p);
        fprintf(g,"%i\n",rez);
	
	}
     
	}

fclose(f);
fclose(g);
return 0;
}