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

void ce()
{
/*	if (x[poz]==2&&poz==n) {b=1;a=0;poz=101;} else
	if (x[poz]==1&&x[poz+1]==2&&poz+2==n) {b=1;a=0;poz=101;} else
*/
	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)
	{
	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 (x[poz]==2||x[poz]==1)
				{
				be();
				a=1;
				}
				else
				if (x[poz]==3)
				{
					poz++;
					be();
					ce();
					a=1;
				}          else
				if (x[poz]==2&&n==poz&&c) {b=1;a=0;poz=101;} else
				if (x[poz]==1&&x[poz+1]==2&&poz+2==n&&c) {b=1;a=0;poz=101;}
*/
				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 (b) printf("1\n"); else printf("0\n");
		}

	}


	return 0;
}