#include<fstream>
#include<iostream>
#include<cstring>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
char sir[10005];
char posib[4][4][6];
short nrPos[4];
short poateFi(short n, short indice, char trebuie[])//verifica daca de la indicele i (in sir) poate urma
//scucesiunea trebuie si returneaza la ce indice se termina sau -1 daca nu se poate
{
	if(indice > n)
		return -1;
	short curent = indice;
	short i,j;
	short litera;
	for(i = 0; i < strlen(trebuie); i++)
	{
		if(sir[curent] == trebuie[i] || trebuie[i] == 'A')
		{
			curent++;
			continue;
		}
		if(sir[curent] != trebuie[i] && (trebuie[i] - '0' <= 3 && trebuie[i] - '0' >= 1))
		{
			return -1;
		}
		litera = trebuie[i] - 'A' + 1; // 1 , 2 , sau 3 pt A sau B sau C
		for(j = 1; j <= nrPos[litera]; j++)
		{
			if(sir[curent] == posib[litera][j][0])
			{
				curent = poateFi(n,curent + 1,posib[litera][j] + 1);
				if(curent == -1)
					return -1;
			}
		}
	}
	return curent;
}
bool verif(short n)
{
	if(n == 1)
		return 1;
	short i,lit;
	switch(sir[1] - '0')
	{
	case 1:
		if(poateFi(n,2,posib[2][2] + 1) == n + 1)
			return 1;
		if(poateFi(n,2,posib[3][3] + 1) == n + 1)
			return 1;
		break;
	case 2:
		if(poateFi(n,2,posib[2][1] + 1) == n + 1)
			return 1;
		break;
	case 3:
		if(poateFi(n,2,posib[3][2] + 1) == n + 1)
			return 1;
		break;
	}
	return 0;
}
int main()
{
	nrPos[1] = 3;
	nrPos[2] = 2;
	nrPos[3] = 3;
	strcpy(posib[1][1],"1");
	strcpy(posib[1][2],"2");
	strcpy(posib[1][3],"3");
	strcpy(posib[2][1],"2B");
	strcpy(posib[2][2],"1A3AC");
	strcpy(posib[3][1],"2");
	strcpy(posib[3][2],"3BC");
	strcpy(posib[3][3],"12A");
	short n,t,bla,i;
	fin>>t;
	for(bla = 1; bla <= t; bla++)
	{
		fin>>n;
		for(i = 1; i <= n; i++)
			fin>>sir[i];
		sir[n + 1] = 0;
		fout<<verif(n)<<'\n';
	}
}