// Perle, clasa a 10-a, Olimpiada Judeteana 2004

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <cstdlib>
#include <cstring>

int ntests;
char available[10001], desired[10001];

void Replace(int i, const char *pearls) {
	int nmoving = strlen(pearls), j;
	for (j = strlen(available); j > i; j --) {
		available[j + nmoving - 1] = available[j];
	}
	for (j = i; j < i + nmoving; j ++) {
		available[j] = pearls[j - i];
	}
}

bool Test(const char *startpearl) {
	strcpy(available, startpearl);
	int i;
	for (i = 0; i < strlen(desired); i ++) { // parcurg perlele
		if (i >= strlen(available)) { // daca nu mai am perle pe care le pot transforma
			return false;
		}
		if (available[i] == desired[i]) { // daca perla pe care o am e deja cea pe care o vreau
			continue;
		}
		switch (available[i]) { // tratez fiecare caz in parte
			case 'A': {
				switch (desired[i]) {
					case '1': {
						Replace(i, "1");
						break;
					}
					case '2': {
						Replace(i, "2");
						break;
					}
					case '3': {
						Replace(i, "3");
						break;
					}
				}
				break;
			}
			case 'B': {
				switch (desired[i]) {
					case '1': {
						Replace(i, "1A3AC");
						break;
					}
					case '2': {
						Replace(i, "2B");
						break;
					}
					case '3': {
						return false;
						break;
					}
				}
				break;
			}
			case 'C': {
				switch (desired[i]) {
					case '1': {
						Replace(i, "12A");
						break;
					}
					case '2': {
						Replace(i, "2");
						break;
					}
					case '3': {
						Replace(i, "3BC");
						break;
					}
				}
				break;
			}
			default: {
				return false;
				break;
			}
		}
	}
	if (strcmp(available, desired) == 0) {
		return true;
	}
	return false;
}

int main(void) {
	FILE *in = fopen("perle.in", "r"), 
		*out= fopen("perle.out", "w");
	fscanf(in, "%d", &ntests);
	int i;
	for (i = 0; i < ntests; i ++) {
		int nlen; // citirea unei secvente dorite
		strcpy(desired, "");
		fscanf(in, "%d", &nlen);
		int j;
		for (j = 0; j < nlen; j ++) {
			fscanf(in, " %c", &desired[j]); // spatiu inainte de %c ca sa sara peste el si sa citeasca doar cifra/perla
		}
		desired[j] = 0;
		
		bool canget = false;
		canget = Test("A");
		if (canget == true) { // incerc cu fiecare perla magica la rand sa obtin secventa dorita, oprind incercarile daca reusesc
			fprintf(out, "1\n");
			continue;
		}
		canget = Test("B");
		if (canget == true) {
			fprintf(out, "1\n");
			continue;
		}
		canget = Test("C");
		if (canget == true) {
			fprintf(out, "1\n");
			continue;
		}
		fprintf(out, "0\n");
	}
	
	fclose(in), fclose(out);
/*
	strcpy(available, "2B");
	Replace(1, "1A3AC");*/

	return 0;
}