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

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

char perle[MAXLEN];
int len, pos;

int incearca_A(void)
{
	if (len == 1)
		return 1;
	return 0;
}

int incearca_B(void)
{
	/* Sanity check */
	if (pos >= len)
		return 0;

	while (perle[pos] == '2')
		pos++;
	if ((perle[pos] == '1') && (perle[pos + 2] == '3'))
	{
		pos+= 4;
		if (incearca_C() == 1)
			return 1;
	}

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

int incearca_C(void)
{
	/* Sanity check */
	if (pos >= len)
		return 0;

	/* Try for final 2 | 12X sequence */
	if (perle[pos] == '2')
	{
		pos++; 
		return 1;
	}
	else if ((perle[pos] == '1') && (perle[pos+1] == '2'))
	{
		pos+= 3;
		return 1;
	}
	/* It should match 3BC or it won't match anything */
	else if (perle[pos] == '3') 
	{
		pos++;
		if (incearca_B() != 1)
			return 0;
		if (incearca_C() != 1)
			return 0;

		return 1;
	}

	/* No match found */
	return 0;
}

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

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

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

	for (sirag = 0; sirag < num_siraguri; sirag++)
	{
		memset((void *)perle, 0, MAXLEN * sizeof(char));
		fscanf(fin, "%d", &len);
		for (i = 0; i < len; i++)
			fscanf(fin, " %c", perle + i);
		pos = 0;

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

		if ((incearca_B() == 1) && (pos == len))
		{
			fprintf(fout, "1\n");
			continue;
		}

		pos = 0;
		if ((incearca_C() == 1) && (pos == len))
		{
			fprintf(fout, "1\n");
			continue;
		}

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

	fclose(fin);
	fclose(fout);

	return 0;
}