# include <stdio.h>

int v[10001],n,l;

int verifica()
{int i,maxnc=0;
int nucl=0;
i=1;
do
{if (v[i]==3)
	{
	nucl+=1;maxnc+=1;
	if (i==1) {nucl++;maxnc++;}
	i++;
	while (v[i]==2) i++;
	if (v[i]!=1||v[i+2]!=3) return 0;
	i+=4;
	}
else
	if (i==1)
		{
		nucl=1;maxnc=1;
		while (v[i]==2) i++;
		if (v[i]!=1||v[i+2]!=3) return 0;
		i+=4;
		}
	else
		{
		if (v[i]==2) {nucl--;maxnc--;i++;}
		else if (v[i]==1&&v[i+1]==2) {i+=3;nucl--;maxnc--;}
			else return 0;
		if (maxnc<0) return 0;
		}
} while (i<=l);
if (l==i-1&&nucl==0) return 1;
return 0;
}

int main()
{
int t,i,j;
FILE *f=fopen("perle.in","rr");
FILE *g=fopen("perle.out","w");
fscanf(f,"%d",&n);
for (t=1;t<=n;t++)
	{
	fscanf(f,"%d",&l);
	for (j=1;j<=l;j++)
		fscanf(f,"%d",&v[j]);
	switch (l)
		{
		case 1: fprintf(g,"1\n"); break;
		case 2: fprintf(g,"0\n"); break;
		case 3: fprintf(g,"%d\n",v[1]==1&&v[2]==2); break;
		case 4: fprintf(g,"0\n");break;
		default:
			{fprintf(g,"%d\n",verifica());}
		}
	}
fcloseall();
return 0;
}