#include <stdio.h>
#define nmax 10005

int A[nmax], k, T, okA, okB, okC, N;

int rec(int p)
{
	int ok = 1;

	if (p == 4)
	{
		if (A[k] == 1 || A[k] == 2 || A[k] == 3)
		{
			ok = 1;
		}
		else
			ok = 0;
	}
	else if (p == 5)
	{
		if (A[k] == 2)
		{
			k++;
			ok = rec(5);
		}
		else if (A[k] == 1)
		{
			k++;
			ok = rec(4);
			if (ok)
			{
				k++;
				if (A[k] == 3)
				{
					k++;
					ok = rec(4);
					if (ok)
					{
						k++;
						ok = rec(6);
					}
				}
				else
					ok = 0;
			}
		}
		else
			ok = 0;
	}
	else
	{
		if (A[k] == 2)
			ok = 1;
		else if (A[k] == 3)
		{
			k++;
			ok = rec(5);
			if (ok)
			{
				k++;
				ok = rec(6);
			}
		}
		else if (A[k] == 1)
		{
			k++;
			if (A[k] == 2)
			{
				k++;
				ok = rec(4);
			}
			else
				ok = 0;
		}
		else
			ok = 0;
	}

	return ok;
}

int main()
{
	freopen("perle.in", "r", stdin);
	freopen("perle.out", "w", stdout);

	scanf("%d\n", &T);

	while (T--)
	{
		scanf("%d", &N);

		for (k = 1; k <= N; ++k)
			scanf("%d", &A[k]);

		k = 1;
		okA = rec(4);
		if (k != N) okA = 0;
		if (okA == 0)
		{
			k = 1;
			okB = rec(5);
			if (k != N) okB = 0;
			if (okB == 0)
			{
				k = 1;
				okC = rec(6);
				if (k != N) okC = 0;
			}
		}
		if (okA || okB || okC)
			printf("1\n");
		else
			printf("0\n");
	}

	return 0;
}