//6 36
#include<iostream>
#include<fstream>
using namespace std;
char x[10001];
bool R(char* t)
{
	if(strlen(x)==1)
		return 1;
	if(strlen(x)<strlen(t))
		return 0;
	if(strlen(x)-1==strlen(t) && t[strlen(t)-1]=='A')
		return 1;
	int a;
	if(strlen(x)==strlen(t) && !strcmp(x,t))
		return 1;
	for(a=0;x[a]==t[a] && a<strlen(t);a++);
	if(x[a]<='3' && x[a]>='1' && t[a]<='3' && t[a]>='1')
		return 0;
	if(x[a]=='1')
	{
		if(t[a]==0 && a==0)
			return (R(strcat(t,"1A3AC")) || R(strcat(t,"12A")));
		if(t[a]=='A')
		{
			t[a]='1';
			return R(t);
		}
		if(t[a]=='B')
		{
			t[strlen(t)-1]=0;
			for(int b=strlen(t)+3;b>=a+5;b--)
				t[b]=t[b-5];
			t[a]='1';
			t[a+1]='A';
			t[a+2]='3';
			t[a+3]='A';
			t[a+4]='C';
			return R(t);
		}
		if(t[a]=='C')
		{
			for(int b=strlen(t)+1;b>=a+3;b--)
				t[b]=t[b-2];
			t[a]='1';
			t[a+1]='2';
			t[a+2]='A';
			return R(t);
		}
		return 0;
	}
	if(x[a]=='2')
	{
		if(t[a]==0 && a==0)
			return R(strcat(t,"2B"));
		if(t[a]=='A' || t[a]=='C')
		{
			t[a]='2';
			return R(t);
		}
		if(t[a]=='B')
		{
			for(int b=strlen(t);b>=a+2;b--)
				t[b]=t[b-1];
			t[a]='2';
			t[a+1]='B';
			return R(t);
		}
		return 0;
	}
	if(x[a]=='3')
	{
		if(t[a]==0 && a==0)
			return R(strcat(t,"3BC"));
		if(t[a]=='C')
		{
			for(int b=strlen(t)+1;b>=a+3;b--)
				t[b]=t[b-2];
			t[a]='3';
			t[a+1]='B';
			t[a+2]='C';
			return R(t);
		}
		if(t[a]=='A')
		{
			t[a]='3';
			return R(t);
		}
		return 0;
	}
}
int main()
{
	ifstream fin("perle.in");
	ofstream fout("perle.out");
	long a,b,n,m;
	char f[10001];
	fin>>n;
	for(a=1;a<=n;a++)
	{
		fin>>m;
		for(b=0;b<m;b++)
			fin>>x[b];
		fout<<R(f)<<endl;
		memset(x, 0, sizeof(x));
		memset(f, 0, sizeof(x));
	}
}