#include <string>
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

string s,sol;
int n,l;
bool bec;

ifstream f("perle.in");
ofstream g("perle.out");

void modificaA(int pos);
void modificaB(int pos);
void modificaC(int pos);


void fct() {
	int i;
	
	if (s==sol) {
		g<<1<<endl;
		bec=true;
	}
	else 
	if (s.size()<=l)
	for (i=0; i<s.size(); i++)
		if (s[i]=='A')
			modificaA(i);
		else
			if (s[i]=='B')
				modificaB(i);
			else
				if (s[i]=='C')
					modificaC(i);
}
void modificaA(int pos) {
	string s1;
	if (bec)
		return;
	s.erase(pos,1);
	s1=s;
	s.insert(pos,"1");
	fct();
	if (bec)
		return;
	s=s1;
	s.insert(pos,"2");
	fct();
	if (bec)
		return;
	s=s1;
	s.insert(pos,"3");
	fct();
}
void modificaB(int pos) {
	string s1;
	if (bec)
		return;
	s.erase(pos,1);
	s1=s;
	s.insert(pos,"2B");
	fct();
	if (bec)
		return;
	s=s1;
	s.insert(pos,"1A3AC");
	fct();
	s=s1;
}
void modificaC(int pos) {
	string s1;
	if (bec)
		return;
	s.erase(pos,1);
	s1=s;
	s.insert(pos,"2");
	fct();
	if (bec)
		return;
	s=s1;
	s.insert(pos,"3BC");
	fct();
	if (bec)
		return;
	s=s1;
	s.insert(pos,"12A");
	fct();
}
int main() {
	f>>n;
	for (int i=1; i<=n; i++){
	bec=false;
	f>>l;
	f>>sol;
	s="A";
	fct();
	if (!bec) {
	s="B";
	fct();
	}
	if (!bec) {
	s="C";
	fct();
	}
	if (!bec)
		g<<0<<endl;
	}
	g.close();
	return 0;
}