#include<stdio.h>
long q,x[20006],l,poz,i,j,k,n,m,N,a,c,b;
void be()
{
	q=1;
	while (x[poz]==2)
	{
	poz++;
	if (poz==n) b=1;
	}
	if (x[poz]==1&&x[poz+2]==3&&poz+2<n) {poz+=4;c++;a=1;}else
	if (x[poz]==2&&poz==n) {b=1;a=0;poz=n+1;}  else
	if (x[poz]==1&&x[poz+1]==2&&poz+2==n) {b=1;a=0;poz=n+1;} else
	q=0;

}

void ce()
{

	if (x[poz]==2&&poz==n) {poz++;b=1;} else
	if (x[poz]==1&&x[poz+1]==2&&poz+2==n) {poz+=3; b=1;}
	if (x[poz]==2) poz++; else
	if (x[poz]==1&&x[poz+1]==2) poz+=3;// else
/*	{
	poz++;
	if (poz<=n)
	{
//	while (q)

	be();
	if (poz<=n)
	ce();
	c=1;
	}
	}
*/
}
int main()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	scanf("%ld",&N);
	for (l=1;l<=N;l++)
	{
		scanf("%ld",&n);
		for (i=1;i<=n;i++)
		{
			scanf("%ld",&x[i]);
			x[i+n]=0;
		}
		if (n==1&&x[1]==1) printf("1\n"); else
		if (n==1&&x[1]==2) printf("1\n"); else
		if (n==1&&x[1]==3) printf("1\n"); else
		if ((n==3&&x[1]==1&&x[2]==2)&&(x[3]==1||x[3]==2||x[3]==3)) printf("1\n"); else
		{
			poz=1;
			a=1;
			b=0;
			while (a)
			{

			a=0;

/*
				if (c==1) {c=0; ce();}
				if ((poz==n&&x[poz]==2)||(poz==n-2&&x[poz]==1&&x[poz+1]==2)) {b=1; poz=n+1;} else
				if (x[poz]==2||x[poz]==1) be();
				if (x[poz]==2||x[poz]==3) ce();
				if (poz>=n) a=0;

*/				if (x[poz]==3)
				{
					q=1;
					c=0;
					poz++;
					while (q) {be(); if (x[poz]==3) poz++;}
					for (i=1;i<=c;i++)
					ce();
				}        else

				if (x[poz]==1||x[poz]==2)
				{
					be();
					be();
				}

			}
			if (b) printf("1\n"); else printf("0\n");
		}

	}


	return 0;
}