#include <stdio.h>
#define DIM 10011

int N,i,e,T,t;
char X[DIM];

void C();
void B();

int main(){
	FILE *f = fopen("perle.in","r");
	FILE *g = fopen("perle.out","w");
	fscanf(f,"%d",&T);
	for (t=1;t<=T;t++){
		fscanf(f,"%d",&N);
		for (i=0;i<N;++i)
			fscanf(f," %c",&X[i]);
		if ((N==1)||((N==3)&&(X[0]=='1')&&(X[1]=='2'))) { 
			fprintf(g,"1\n");
			continue; 
		}
		e=1;
		if ((X[0]=='1')&&(X[2]=='3')) { 
			i=4;
			C(); 
		} else 
			if (X[0]=='2') { 
				i=1;
				B(); 
			} else 
				if (X[0]=='3') { 
					i=1;
					B();
					C(); 
				} else 
					e=0;
		if (i!=N) 
			e=0;
		fprintf(g,"%d\n",e);
	}
	fclose(f);
	fclose(g);
	return 0;
}

void B(){
	while ((i<N)&&(X[i]=='2')) 
		++i;
	if (i>=N)
		e=0;
	else 
		if ((X[i]=='1')&&(X[i+2]=='3')){
			i+=4;
			C(); 
		}
		else
			e=0;
}

void C(){
	if (i>=N)
		e=0;
	else
		if (X[i]=='3') { 
			++i;
			B();
			C(); 
		} else 
			if ((X[i]=='1')&&(X[i+1]=='2'))
				i+=3;
			else 
				if (X[i]=='2')
					++i;
				else
					e=0;
}