#include <stdio.h>

int v[10002], vtmp[10002];

int rezolvaB(int);
int rezolvaC(int);

int rezolvaB(int in)
{
	if (in>=v[0]) return 0;
	if (v[in]==2)
	{
		vtmp[in]=2;
		vtmp[in+1]=5;
		return rezolvaB(in+1);
	}
	else if (v[in]==1)
	{
		vtmp[in]=1;
		vtmp[in+1]=4;
		vtmp[in+2]=3;
		vtmp[in+3]=4;
		vtmp[in+4]=6;
		return rezolvaC(in+4);
	}
	return rezolvaC(in+1);
}

int rezolvaC(int in)
{
	int i;
	if (in>v[0]) return 0;
	if (v[in]==2 && in==v[0]) return 1;
	else if (v[in]==1)
	{
		vtmp[in]=1;
		vtmp[in+1]=2;
		vtmp[in+2]=4;
		for (i=1; i<=v[0]; i++)
			if (v[i]!=vtmp[i] && vtmp[i]!=4) return 0;
		return 1;
	}
	else if (v[in]==3)
	{
		if (v[v[0]]==2)
		{
			v[0]--;
			return rezolvaB(in+1);
		}
		else if (v[v[0]-1]==2 && v[v[0]-2]==1)
		{
			v[0]-=3;
			return rezolvaB(in+1);
		}
	}
	return 0;
}

int rezolva()
{
	if (v[0]==1) return 1;
	else if (v[0]==2) return 2;
	if (v[1]==3) return rezolvaC(1);
	return rezolvaB(1);
}

int main()
{
	freopen("perle.in", "rt", stdin);
	freopen("perle.out", "wt", stdout);
	int n, i, j;
	scanf("%d\n", &n);
	for (i=0; i<n; i++)
	{
		scanf("%d ", &v[0]);
		for (j=1; j<=v[0]; j++) scanf("%d ", &v[j]);
		printf("%d\n", rezolva());
		scanf("\n");
	}

	return 0;
}