#include <fstream>
#include <string>
using namespace std;

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

int n,nr;
char s[10007];

bool r1A3AC() {
	if (nr < 5) return false;
	if ((s[nr] == 'C' || s[nr] == '2') && (s[nr-1]=='1'||s[nr-1]=='2'||s[nr-1]=='3'||s[nr-1]=='A')&&(s[nr-2]=='3'||s[nr-2]=='A')&&
		(s[nr-3]=='1'||s[nr-3]=='2'||s[nr-3]=='3'||s[nr-3]=='A')&&(s[nr-4]=='1'||s[nr-4]=='A')){
			nr -= 4;
			s[nr] = 'B';
			return true;
		}
	return false;
}

bool r2B () {
	if(nr < 2) return false;
	if (s[nr] == 'B' && (s[nr-1] == '2' || s[nr-1]=='A')){
		nr -= 1;
		s[nr] = 'B';
		return true;
	}
	return false;
}

bool r3BC () {
	if (nr < 3) return false;
	if ((s[nr] == 'C' ||s[nr]=='2')&&s[nr-1]=='B'&&(s[nr-2]=='3'||s[nr-2]=='A')){
		nr -= 2;
		s[nr] = 'C';
		return true;
	}
	return false;
}

bool r12A() {
	if (nr < 3) return false;
	if ((s[nr] == 'A' || s[nr] == '1' || s[nr]=='2'||s[nr]=='3')&&(s[nr-1]=='2'||s[nr-1]=='A')&&(s[nr-2]=='1'||s[nr-2]=='A')){
		nr -= 2;
		s[nr] = 'C';
		return true;
	}
	return false;
}

void redu () {
	if (r1A3AC() || r2B() || r3BC() || r12A()) {
		redu();
	}
}

void jfkduisfbuis() {
	int x;
	char ch;
	in >> x;
	
	for (int i = 1; i <= x; ++i) {
		in >> ch;
		s[++nr] = ch;
		redu();
	}
	in>>ws;
	if (nr == 1) out << "1\n";
	else out << "0\n";
	
	nr = 0;
}

void citire () {
	in >> n >> ws;
	while (n--) {
		jfkduisfbuis();
	}
}

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