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

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

char perle[MAXLEN];

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;
}

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;
}