//6 36
#include<iostream>
#include<fstream>
#include <stdio.h>
#include <string.h>
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;
	if(strlen(x)-1==strlen(t) && t[strlen(t)-1]=='C' && x[strlen(x)-1]=='2')
		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')
		{
			char p[1000];
			strcpy(p,t+a+1);
			for(int b=a;b-a<=12;b++)
				t[a]=0;
			for(int b=strlen(t)+4;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';
			strcat(t,p);
			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]='2';
			return R(t);
		}
		if(t[a]=='C')
		{
			char o[10001];
			strcpy(o,t);
			o[a]='2';
			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)|| R(o));
		}
		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));
	}
}