#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;
}