/*
	De pe Infoarena - http://infoarena.ro/problema/perle

	Perle

Granita nu se trece usor. Asta pentru ca Balaurul Arhirel (mare pasionat de informatica) nu lasa pe nimeni sa treaca decat dupa ce raspunde la niste intrebari!

In acea tara exista 3 tipuri de perle normale (le vom nota cu 1, 2 si 3) si 3 tipuri de perle magice (le vom nota cu A, B si C). Perlele magice sunt deosebite prin faptul ca se pot transforma in alte perle (una sau mai multe, normale sau magice).

Perla magica de tipul A se poate transforma in orice perla normala (una singura).

Perla magica de tipul B se poate transforma intr-o perla normala de tipul 2 si una magica de tipul B, sau intr-o perla normala de tipul 1, una magica de tipul A, una normala de tipul 3, una magica de tipul A si una magica de tipul C.

Perla magica de tipul C se poate transforma intr-o perla normala de tipul 2 sau intr-o perla normala de tipul 3, una magica de tipul B si una magica de tipul C sau intr-o perla normala de tipul 1, una normala de tipul 2 si una magica de tipul A.

Ca sa rezumam cele de mai sus putem scrie:

       A -> 1 | 2 | 3
       B -> 2B | 1A3AC
       C -> 2 | 3BC | 12A

Balaurul Arhirel ne lasa la inceput sa ne alegem o perla magica (una singura), iar apoi folosind numai transformarile de mai sus trebuie sa obtinem un anumit sir de perle normale. Cand o perla magica se transforma, perlele din stanga si din dreapta ei raman la fel (si in aceeasi ordine). De asemenea ordinea perlelor rezultate din transformare este chiar cea prezentata mai sus.

De exemplu, daca balaurul ne cere sa facem sirul de perle 21132123, putem alege o perla magica de tipul B si urmatorul sir de transformari: B -> 2B -> 21A3AC -> 21A3A12A -> 21132123.

Deoarece Balaurul nu are prea multa rabdare, el nu ne cere decat sa spunem daca se poate sau nu obtine sirul respectiv de perle.
Cerinta

Sa se determine pentru fiecare sir de intrare daca se poate obtine prin transformarile de mai sus sau nu (alegand orice prima perla magica, la fiecare sir).
Date de intrare

Fisierul de intrare perle.in are urmatoarea structura: pe prima linie numarul N, reprezentand numarul de siruri din fisierul de intrare. Urmeaza N linii; a i-a linie dintre cele N descrie sirul i, printr-o succesiune de numere naturale despartite de cate un spatiu. Primul numar reprezinta lungimea sirului, Li, iar urmatoarele Li numere sunt tipurile de perle normale, in ordine, de la stanga la dreapta.
Date de iesire

Fisierul de iesire perle.out va contine N linii. Pe linia i se va scrie un singur numar 1 sau 0 (1 daca se poate obtine sirul al i-lea si 0 daca nu se poate).
Restrictii si precizari

    * 0 < N < 11
    * 0 < Li < 10 001, pentru i de la 1 la N

*/
#include <stdio.h>
#include <string.h>

#define IN_FILE "perle.in"
#define OUT_FILE "perle.out"
#define MAXLEN 10005

char perle[MAXLEN];

/*
 * Error codes:
	                   0 - OK
	                  -1 - not OK
	other positive value - current pos for B
*/

int incearca_A(pos, len)
{
	//printf("Trying A\n");
	if (len == 1)
	{
		//printf("Matches simple A\n");
		return 0;
	}
	//printf("Doesn't match simple A\n");
	return -1;
}

int incearca_B(pos, len)
{
	//printf("Trying B\n");
	/* Sanity check */
	if (pos >= len)
	{
		//printf("Surpassed length trying B!");
		return -1;
	}

	while (perle[pos] == '2')
		pos++;
	if ((perle[pos] == '1') && (perle[pos + 2] == '3'))
	{
		//printf("matches 1x3x; trying C\n");
		if (incearca_C(pos + 4, len) != -1)
			return 0;
	}

	/* This means the string didn't match the form of B */
	return -1;
}

int incearca_C(pos, len)
{
	int found_c = 0;

	//printf("Trying C\n");
	/* Sanity check */
	if (pos >= len)
	{
		//printf("Surpassed length trying C - pos = %d, len = %d!", pos, len);
		return -1;
	}

	if (((len - pos) == 1) && perle[pos] == '2')
	{
		//printf("Matches 2 - we're cool !\n");
		return 1;
	}

	if (((len - pos) == 3) && (perle[pos] == '1') && (perle[pos+1] == '2'))
	{
		//printf("Matches 12X - we're cool !\n");
		return 3;
	}

	if (perle[pos] == '3')
	{
		//printf("Matches 3BC\n");
		pos++;

		/* Now try to find a 2*1x3xC sequence */
		while (perle[pos] == '2')
			pos++;
		if ((perle[pos] == '1') && (perle[pos + 2] == '3'))
			 found_c = incearca_C(pos + 4, len);

		if (found_c > 0)
			return (incearca_C(pos + found_c, len));
	}


	/* No match found */
	return -1;
}

/* Exista vreo posibilitate de backtracking tinand cont de transformari ?! 
 * Adica la un moment dat in parsare se poate sa ajung la o situatie care (pe moment) poate avea mai multe solutii ?
	(iar dupa o parcurgere ulterioara unele din ele se vor dovedi gresite si va trebui sa incerc din nou?)
 * CRED ca nu !
	- de fapt vad un caz, dar doar pentru siruri de lungime 1 (deci nu ma intereseaza, fiindca oricum va cadea in cazul A)

 * Transformarile intr-o forma mai prietenoasa:
	A -> 1 | 2 | 3
	B -> 2B | 1x3xC
	C -> 2 | 12X | 3BC
 */

int main(void)
{
	int sirag, num_siraguri, i, lungime_sirag;
	FILE *fin, *fout;

	fin = fopen(IN_FILE, "r");
	fout = fopen(OUT_FILE, "w");

	fscanf(fin, "%d\n", &num_siraguri);
	//printf("num_siraguri = %d\n", num_siraguri);

	for (sirag = 0; sirag < num_siraguri; sirag++)
	{
		//printf("\n\nUrmatorul sirag\n");
		memset((void *)perle, 0, MAXLEN * sizeof(char));
		fscanf(fin, "%d", &lungime_sirag);
		//printf(" are lungimea %d\n", lungime_sirag);
		for (i = 0; i < lungime_sirag; i++)
			fscanf(fin, " %c", perle + i);
		//printf("Ultima perla din sir: %c\n", perle[lungime_sirag - 1]);

		if (incearca_A(0, lungime_sirag) != -1)
		{
			fprintf(fout, "1\n");
			continue;
		}

		if (incearca_B(0, lungime_sirag) != -1)
		{
			fprintf(fout, "1\n");
			continue;
		}
		if (incearca_C(0, lungime_sirag) != -1)
		{
			fprintf(fout, "1\n");
			continue;
		}

		fprintf(fout, "0\n");
			
	}

	fclose(fin);
	fclose(fout);

	return 0;
}