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

int match(char *s,	char ch)
{	int t,t0;
	if (ch=='A')
	{	if(s[0]=='1'||s[0]=='2'||s[0]=='3')
		{	return 1;
		}
	}
	else if (ch=='B')
	{	if(s[0]=='1'&&match(s+1,'A')&&s[2]=='3'&&match(s+3,'A')&&(t=match(s+4,'C')))
		{	
			return 4+t;
		}
		else if(s[0]=='2'&&(t=match(s+1,'B')))
		{	
			return 1+t;	
		}
	}
	else if (ch=='C')
	{	if(s[0]=='2')
		{	return 1;	
		}
		else if(s[0]=='3'&&(t=match(s+1,'B'))&&(t0=match(s+t+1,'C')))
		{	return 1+t+t0;
		}	
		else if(s[0]=='1'&&s[1]=='2'&&(t=match(s+2,'A')))
		{	return 2+t; 
		}
	}
	return 0;	
}

int doo(char *s)
{	
	for (char ch='A';ch<='C';ch++)
	{	if((match(s,ch))==strlen(s))
		{	
			return 1;
		}
	}
	return 0;	
}

int main()
{	char s[]="22";
	int n,l;
	char str[10005];
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{	scanf("%d ",&l);		
		int j;
		for(j=0;j<l;j++)
		{	scanf("%c ",&str[j]);
		}
		str[j]=0;
		printf("%d\n",doo(str));
}

	return 0;
}