#include<cstdio>
#define N 20004
char s[N],a[4][2],b[3][6],c[4][4],s1[N/2];
int v[N/2],n,h;
void mat_c(int,int);
void mat_b(int,int);
bool ok=false;
void sir()
{
	int cn=n-1,num=1;
	cn*=2;
	for (int i=0; i<=cn; i+=2)
		s1[num++]=s[i];
	s1[num]=0;	
	s1[0]=' ';
}
void matrice()
{
	a[0][0]=3;
	a[1][0]=a[2][0]=a[3][0]=1;
	a[1][1]='1';
	a[1][2]='2';
	a[1][3]='3';
	b[0][0]=2;
	b[1][0]=2;b[2][0]=5;
	b[1][1]='2';b[1][2]='B';
	b[2][1]='1';b[2][2]='A';b[2][3]='3';b[2][4]='A';b[2][5]='C';
	c[0][0]=3;
	c[1][0]=1;c[1][1]='2';
	c[2][0]=3;c[2][1]='3';c[2][2]='B';c[2][3]='C';
	c[3][0]=3;c[3][1]='1';c[3][2]='2';c[3][3]='A';
	
}
void potriveste(int x)
{
	int cx=x;
	if (s1[x]=='3')
	{
		if (x+c[2][0]-1<=n&&!ok)
		mat_c(x,2);
		if (!ok)
			x=cx;
	}
	else
		if (s1[x]=='2')
		{
			if (x+c[1][0]-1<=n&&!ok)
			mat_c(x,1);
			if (!ok)
				x=cx;
			
			if (x+b[1][0]-1<=n&&!ok)
			mat_b(x,1);
			if (!ok)
				x=cx;
		}
		else
			if (s1[x]=='1')
			{
				if (x+c[3][0]-1<=n&&!ok)
				mat_c(x,3);
				if (!ok)
				x=cx;
				
				if (x+b[2][0]-1<=n&&!ok)
				mat_b(x,2);
				if (!ok)
				x=cx;
				
			}
}
void mat_c(int x, int y)
{
	int cx=x;
	for (int i=1; i<=c[y][0]; ++i)
	{
		if (s1[x]==c[y][i]||c[y][i]=='A')
		{
			++x; 
			continue;
		}
		if (c[y][i]=='B')
		{
			if (s1[x]=='2'&&x+b[1][0]-1<=n)
			{
				mat_b(x,1);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+b[2][0]-1<=n)
			{
				mat_b(x,2);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			//potriveste(x);
		}
		if (c[y][i]=='C')
		{
			if (s1[x]=='2'&&x+c[1][0]-1<=n)
			{
				mat_c(x,1);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='3'&&x+c[2][0]-1<=n)
			{
				mat_c(x,2);
				if (!ok){
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+c[3][0]-1<=n)
			{
				mat_c(x,3);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
		}
	}
	if (n==x-1)
		ok=true;
}
void mat_b(int x, int y)
{
	int cx=x;
	for (int i=1; i<=b[y][0]&&x<=n; ++i)
	{
		if (s1[x]==b[y][i]||b[y][i]=='A')
		{
			++x; 
			continue;
		}
		if (b[y][i]=='B')
		{
			if (s1[x]=='2'&&x+b[1][0]-1<=n)
			{
				mat_b(x,1);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+b[2][0]-1<=n)
			{
				mat_b(x,2);
				if (!ok){
				x=cx;//x1=cx1;
				}
			}
			//potriveste(x);
		}
		if (b[y][i]=='C')
		{
			if (s1[x]=='2'&&x+c[1][0]-1<=n)
			{
				mat_c(x,1);
				if (!ok){
				x=cx;//x1=cx1;
				}
			}
			if (s1[x]=='3'&&x+c[2][0]-1<=n)
			{
				mat_c(x,2);
				if (!ok){
				x=cx;//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+c[3][0]-1<=n)
			{
				mat_c(x,3);
				if (!ok){
				x=cx;
				//x1=cx1;
				}
			}
		}
	}
	if (n==x-1)
		ok=true;
}

void citire()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	int nr;
	scanf("%d",&nr);
	while (nr)
	{
		scanf("%d ",&n);
		fgets(s,N,stdin);
		sir();
		ok=false;
		potriveste(1);
		if (ok||n==1)
			printf("1\n");
		else
			printf("0\n");
		//printf("%s\n",s1);
		--nr;
	}
}
int main()
{
	matrice();
	citire();
	return 0;
}