#include <cstdio>

const int MAX_SIZE(10001);

int n, l;
char v [MAX_SIZE];

int b (const int index);
int c (const int index);

int b (const int index)
{
	if (index > l)
		return 0;
	if (v[index] == '2')
		return b(index + 1);
	if (index + 2 <= l && v[index] == '1' && v[index + 2] == '3')
		return c(index + 4);
	return 0;
}

int c (const int index)
{
	if (index > l)
		return 0;
	if (v[index] == '2')
		return index;
	if (v[index] == '3')
	{
		const int jump(b(index + 1));
		if (jump)
			return c(jump + 1);
	}
	if (index + 2 <= l && v[index] == '1' && v[index + 1] == '2')
		return index + 2;
	return 0;
}

int main (void)
{
	std::freopen("perle.in","r",stdin);
	std::freopen("perle.out","w",stdout);
	std::scanf("%d\n",&n);
	char *iterator, *end;
	while (n)
	{
		std::scanf("%d ",&l);
		for (iterator = v + 1, end = v + l ; iterator <= end ; ++iterator)
			std::scanf("%c ",iterator);
		std::scanf("\n");
		if (l == 1 || b(1) == l || c(1) == l)
			std::putchar('1');
		else
			std::putchar('0');
		std::putchar('\n');
		--n;
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}