#include <fstream.h>
#include <string.h>
int n,l;
char s[10009],x[10009],a[3][2]={{'1'},{'2'},{'3'}},b[2][6]={{"2B"},{"1A3AC"}},c[3][4]={{"2"},{"3BC"},{"12A"}};
ofstream fout("perle.out");


void afis(int i)
{
	fout<<i<<'\n';
}

int caut(int r,char x,int &i,int &w)
{
	int l,sw=0;
	if(w>0)
	{
		if(w==1)
		{
			for(l=0;l<3 && !sw;l++)
			if(a[l][0]==x && strlen(a[l])>=r)
			{
				sw=1;
				w=1; i=l;
			}
			if(sw)
				return 1;
		}
		if(w==2)
		{
			for(l=0;l<2 && !sw;l++)
				if(b[l][0]==x && strlen(b[l])>=r)
				{
					sw=1;
					w=2; i=l;
				}
			if(sw)
				return 1;
		}
		if(w==3)
		{
			for(l=0;l<3 && !sw;l++)
				if(c[l][0]==x && strlen(c[l])>=r)
				{
					sw=1;
					w=3; i=l;
				}
			if(sw)
				return 1;
		}
	}
	else
	{
	for(l=0;l<3 && !sw;l++)
		if(a[l][0]==x && strlen(a[l])>=r)
		{
			sw=1;
			w=1; i=l;
		}
	if(sw)
		return 1;
	else
	{
		for(l=0;l<2 && !sw;l++)
			if(b[l][0]==x && strlen(b[l])>=r)
			{
				sw=1;
				w=2; i=l;
			}
		if(sw)
			return 1;
		else
		{
			for(l=0;l<3 && !sw;l++)
				if(c[l][0]==x && strlen(c[l])>=r)
				{
					sw=1;
					w=3; i=l;
				}
			if(sw)
				return 1;
		}
	}
	}
	return 0;
}

void insert(int i,int p,int w)
{
	char aux[10005];
	int n;
	if(w==1)
	{
		n=strlen(x);
		strcpy(aux,x+i+1);
		aux[n-i+1]='\0';
		x[i]='\0';
		strcat(x,a[p]);
		strcat(x,aux);
	}
	else
		if(w==2)
		{
			n=strlen(x);
			strcpy(aux,x+i+1);
			aux[n-i+1]='\0';
			x[i]='\0';
			strcat(x,b[p]);
			strcat(x,aux);
		}
		else
		{
			n=strlen(x);
			strcpy(aux,x+i+1);
			aux[n-i+1]='\0';
			x[i]='\0';
			strcat(x,c[p]);
			strcat(x,aux);
		}
}


void rez()
{
	int i,r,sw=1,p,w,t,nr=0;
	char aux[6];
	for(i=0;i<l && sw;i++)
	{
		r=l-i-1;
		if(s[i]!=x[i])
		{
			if(r<=1)
				t=1;
			else
				t=2;
			if(x[i]!='A' && x[i]!='B' && x[i]!='C')
			{
				if(nr<1)
				{
					w=0;
					if(caut(t,s[i],p,w))
						insert(i,p,w);
					else
						sw=0;
					nr++;
				}
				else
					sw=0;
			}
			else
			{
				if(x[i]=='A') w=1;
				if(x[i]=='B') w=2;
				if(x[i]=='C') w=3;
				if(caut(1,s[i],p,w))
					insert(i,p,w);
				else
					sw=0;
			}
		}
	}
	if(sw && strcmp(x,s)==0)
		afis(1);
	else
		afis(0);
}

void cit()
{
	int i,j;

	ifstream fin("perle.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>l; fin.get();
		for(j=0;j<l;j++)
		{
			s[j]=fin.get(); fin.get();
		}
		s[l]='\0';
		rez();
		for(j=0;j<=l;j++)
		{
			x[j]='\0';
			s[j]='\0';
		}
	}
	fin.close();
}

int main()
{
	cit();
	return 0;
}