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

//	A -> 1 / 2 / 3
//	B -> 2B / 1A3AC
//	C -> 2 / 3BC / 12A

FILE *fi=fopen("perle.in","r"),*fo=fopen("perle.out","w");
int n,lev,ler;
char vec[10000],rez[10000];

void cit(FILE *f,int &n,char vec[])
{
	fscanf(f,"%i",&n);
	for(int i=0;i<n;i++)
		fscanf(f," %c",&vec[i]);
}

void init(char vec[],int lev,char rez[],int &ler)
{
	if(vec[0]=='2')
	{
		rez[0]='2';
		rez[1]='B';
		ler=2;
	}
	if(vec[0]=='3')
	{
		rez[0]='3';
		rez[1]='B';
		rez[2]='C';
		ler=3;
	}
	if(vec[0]=='1')
	{
		rez[0]='1';
		rez[1]='A';
		rez[2]='3';
		rez[3]='A';
		rez[4]='C';
		ler=5;
	}
}

int ifB1(char vec[],int lev,char rez[],int &ler,int &poz)
{
	if(vec[poz]=='1')
	{
		ler+=4;
		rez[poz++]='1';
		rez[poz++]=vec[poz];
		if(vec[poz]=='3')
			rez[poz++]='3';
		else
			return 1;
		rez[poz]=vec[poz];
		rez[poz+1]='C';
		return 0;
	}
	else
		if(vec[poz]=='2')
		{
			ler++;
			rez[poz]='2';
			rez[poz+1]='B';
			return 0;
		}
		else
			return 1;
}

int ifB2(char vec[],int lev,char rez[],int &ler,int &poz)
{
	if(ifB1(vec,lev,rez,ler,poz))
		return 1;
	rez[poz+2]='C';
	return 0;
}

int ifC(char vec[],int lev,char rez[],int &ler,int &pozr)
{
	switch(vec[pozr])
	{
	case '1':
		ler+=2;
		rez[pozr++]='1';
		if(vec[pozr]!='2')
			return 1;
		else
			rez[pozr++]='2';
		rez[pozr]=vec[pozr];
		break;
	case '2':
		rez[pozr]='2';
		break;
	case '3':
		ler+=2;
		rez[pozr+1]='B';
		rez[pozr+2]='C';
		break;
	}
	return 0;
}

int rezs(char vec[],int lev,char rez[],int ler)
{
	int pozr=1;
	while(pozr<ler && pozr<lev)
	{
		switch(rez[pozr])
		{
		case 'A':
			rez[pozr]=vec[pozr];
			break;
		case 'B':
			if(vec[pozr+1]=='C' && pozr+1!=lev)
			{
				if(ifB2(vec,lev,rez,ler,pozr))
					return 0;
			}
			else
				if(ifB1(vec,lev,rez,ler,pozr))
					return 0;
			break;
		case 'C':
			if(ifC(vec,lev,rez,ler,pozr))
				return 0;
			break;
		}
		pozr++;
	}
	if(lev!=ler)
		return 0;
	return 1;
}

int main()
{
	fscanf(fi,"%i",&n);
	for(int i=0;i<n;i++)
	{
		cit(fi,lev,vec);
		if(lev==1 || (vec[0]=='1' && vec[1]=='2' && lev==3))
			fprintf(fo,"1\n");
		else
		{
			init(vec,lev,rez,ler);
			fprintf(fo,"%i\n",rezs(vec,lev,rez,ler));
		}
	}
	return 0;
}