#include <iostream>
#include <fstream>
#include <cstring>
#include <math.h>
using namespace std;
 
char L[10001];
int N,l;
int varianta_2B(char t[],int m,int ok);
int varianta_1A3AC(char t[],int m,int ok);
int perla_B(char t[],int m,int ok);
int varianta_2(char t[],int m,int ok);
int varianta_12A(char t[],int m,int ok);
int varianta_3BC(char t[],int m,int ok);
int perla_C(char t[],int m,int ok);

int perla_A(char t[],int m)
{
	if(m!=l)
		return 0;
	if(strrchr(t,'A')==NULL){
		if(strcmp(L,t)==0)
			return 1;
		else return 0;
	}
	char *p=strrchr(t,'A');
	for(int i=1;i<=3;i++){
		*p=i+'0';
		if(strcmp(L+(p-t),t+(p-t))==0)
			return perla_A(t,m);
	}
	return 0;
}
int varianta_2B(char t[],int m,int ok)
{
	if(m>l)
		return 0;
	t[m++]='2';
	return perla_B(t,m,ok);
}
int varianta_1A3AC(char t[],int m,int ok)
{
	if(m>l)
		return 0;
	t[m++]='1';
	t[m++]='A';
	t[m++]='3';
	t[m++]='A';
	return perla_C(t,m,ok);
}
int perla_B(char t[],int m,int ok)
{
	if(L[l-(l-m)]=='2')
		return varianta_2B(t,m,ok);
	else return varianta_1A3AC(t,m,ok);
	// if(varianta_2B(t,m,ok)==0)
	// 	return varianta_1A3AC(t,m,ok);
	// else return 1;
}
int varianta_2(char t[],int m,int ok)
{
	if(m>l)
		return 0;
	t[m++]='2';
	if(ok>0)
		return perla_C(t,m,ok-1);
	else return perla_A(t,m);
}
int varianta_12A(char t[],int m,int ok)
{
	if(m>l)
		return 0;
	t[m++]='1';
	t[m++]='2';
	t[m++]='A';
	if(ok>0)
		return perla_C(t,m,ok-1);
	else return perla_A(t,m);
}
int varianta_3BC(char t[],int m,int ok)
{
	if(m>l)
		return 0;
	t[m++]='3';
	return perla_B(t,m,ok+1);
}
int perla_C(char t[],int m,int ok)
{
	if(L[l-(l-m)]=='2')
		return varianta_2(t,m,ok);
	else{
		if(L[l-(l-m)]=='1')
			return varianta_12A(t,m,ok);
		else return varianta_3BC(t,m,ok);
	}
	// if(varianta_2(t,m,ok)==0){
	// 	if(varianta_12A(t,m,ok)==0)
	// 		return varianta_3BC(t,m,ok);
	// 	else return 1;
	// }
	// else return 1;
}
int cautare()
{
	char t[10001];
	int m=0;

	if(l==1){
		t[m++]='A';
		return perla_A(t,m);
	}
	if(perla_B(t,m,0)==0)
		return perla_C(t,m,0);
	else return 1;
}
int main()
{
	ifstream in("perle.in");
	ofstream out("perle.out");

    in>>N;
    while(N){
    	in>>l;
    	for(int i=0;i<l;i++)
    		in>>L[i];
    	out<<cautare()<<endl;
    	N-=1;

    }
    
	return 0;
}