#include <iostream>
#include <fstream>

#define LUN_MAX 10001

using namespace std;

char sir[LUN_MAX], sir_verificare[LUN_MAX];
int lin, col, stare, indsir;

struct {
	char comp[7];
} tabel[4][4];

void creare_tabel() {
	tabel[1][1].comp[1] = '1';
	tabel[1][1].comp[2] = '\0';
	tabel[1][2].comp[1] = '2';
	tabel[1][2].comp[2] = '\0';
	tabel[1][3].comp[1] = '3';
	tabel[1][3].comp[2] = '\0';
	tabel[2][1].comp[0] = '2';
	tabel[2][1].comp[1] = '2';
	tabel[2][1].comp[2] = 'B';
	tabel[2][1].comp[3] = '\0';
	tabel[2][2].comp[0] = '5';
	tabel[2][2].comp[1] = '1';
	tabel[2][2].comp[2] = 'A';
	tabel[2][2].comp[3] = '3';
	tabel[2][2].comp[4] = 'A';
	tabel[2][2].comp[5] = 'C';
	tabel[2][2].comp[6] = '\0';
	tabel[2][3].comp[1] = '\0';
	tabel[3][1].comp[1] = '2';
	tabel[3][1].comp[2] = '\0';
	tabel[3][2].comp[0] = '3';
	tabel[3][2].comp[1] = '3';
	tabel[3][2].comp[2] = 'B';
	tabel[3][2].comp[3] = 'C';
	tabel[3][2].comp[4] = '\0';
	tabel[3][3].comp[0] = '3';
	tabel[3][3].comp[1] = '1';
	tabel[3][3].comp[2] = '2';
	tabel[3][3].comp[3] = 'A';
	tabel[3][3].comp[4] = '\0';
}

void copiere_perla(int &indsir, int lin, int col) {
	int i = 1;
	while (tabel[lin][col].comp[i] != '\0') {
		sir_verificare[indsir] = tabel[lin][col].comp[i];
		i++;
		indsir++;
	}
	indsir -= ((int)tabel[lin][col].comp[0]) - 48;
}

void prima_perla(char componenta, int nr_max, int &stare) {
	switch (componenta) {
	case '1': {
		if (nr_max >= 5) {
			lin = 2;
			col = 2;
		}
		else {
			if (nr_max == 3) {
				lin = 3;
				col = 3;
			}
			else {
				stare = 0;
			}
		}
		break;
	}
	case '2': {
		if (nr_max >= 6) {
			lin = 2;
			col = 1;
		}
		else {
			stare = 0;
		}
		break;
	}
	case '3': {
		if (nr_max >= 7) {
			lin = 3;
			col = 2;
		}
		else {
			stare = 0;
		}
		break;
	}
	}
	if (stare) {
		copiere_perla(indsir, lin, col);
	}
}

int verif_litsaucif(char componenta) {
	if (sir_verificare[indsir] == 'A' || sir_verificare[indsir] == 'B' || sir_verificare[indsir] == 'C')
		return 1;
	return 0;
}

void linie(char aleg_lin, int &lin) {
	if (aleg_lin == 'A') {
		lin = 1;
		return;
	}
	else {
		if (aleg_lin == 'B') {
			lin = 2;
			return;
		}
	}
	lin = 3;
}

void coloana(char ind_sir, int lin, int &col, int &stare) {
	int col_mat;
	col = 1;
	if (lin == 2) {
		col_mat = 2;
	}
	else {
		col_mat = 3;
	}
	while (col <= col_mat) {
		if (tabel[lin][col].comp[1] == ind_sir)
			return;
		col++;
	}
	stare = 0;
}

void facem_loc(int lungime_sir1, int lungime_tabel, int indice) {
	int i;
	for (i = lungime_sir1; i >= indice + 1; i--) {
		sir_verificare[i + lungime_tabel - 1] = sir_verificare[i];
	}
}

int lungime_sir(char un_sir[LUN_MAX]) {
	int contor = 0, i = 1;
	while (un_sir[i] != '\0') {
		contor++;
		i++;
	}
	return contor;
}

int exista_lit(char un_sir[LUN_MAX]) {
	int i = 1;
	while (un_sir[i] != '\0') {
		if (verif_litsaucif(un_sir[i])) {
			return 1;
		}
		i++;
	}
	return 0;
}

int verificare_perla(int nr_max) {
	stare = 1; 
	if (nr_max > 1) {
		indsir = 1;
		creare_tabel();
		prima_perla(sir[indsir], nr_max, stare);
		indsir++;
		while (sir[indsir] != '\0' && stare) {
			if (!(verif_litsaucif(sir_verificare[indsir]))) {
				if (sir_verificare[indsir] != sir[indsir]) {
					stare = 0;
				}
			}
			else {
				linie(sir_verificare[indsir], lin);
				coloana(sir[indsir], lin, col, stare);
				if (tabel[lin][col].comp[0] != '\0') {
					if (sir_verificare[indsir + 1] != '\0') {
						facem_loc(lungime_sir(sir_verificare), ((int)tabel[lin][col].comp[0]) - 48, indsir);
					}
					copiere_perla(indsir, lin, col);
				}
				else {
					sir_verificare[indsir] = tabel[lin][col].comp[1];
				}
			}
			indsir++;
		}
	}
	if (!(exista_lit(sir_verificare)) && stare) {
		return 1;
	}
	return 0;
}

void formatam_sir(char un_sir[LUN_MAX]) {
	int i = 1;
	while (un_sir[i] != '\0') {
		un_sir[i] = '\0';
		i++;
	}
}

int main() {
	ifstream intrare("perle.in");
	ofstream iesire("perle.out");
	int numar_de_siruri, lungime_sir_in, i, j;
	intrare >> numar_de_siruri;
	for (i = 1; i <= numar_de_siruri; i++) {
		intrare >> lungime_sir_in;
		for (j = 1; j <= lungime_sir_in; j++) {
			intrare >> sir[j];
		}
		iesire << verificare_perla(lungime_sir_in) << endl;
		formatam_sir(sir);
		formatam_sir(sir_verificare);
	}
	intrare.close();
	iesire.close();
	cout << "Programul a fost executat cu SUCCES!" << endl << "Verificati fisierul perle.out pentru detalii." << endl << endl;
	system("pause");
	return 0;
}