#include<cstdio>
int T,k,nrc,a[10010];
bool perla_b(int poz);
bool perla_c(int poz);
bool perla_a(int poz)
{
	if(poz==k && nrc==0)
		return 1;
	if(nrc)
	{
		nrc--;
		return perla_c(poz+1);
	}
	return 0;
}
bool perla_b(int poz)
{
	if(a[poz]==2 && poz+1<=k)
		return perla_b(poz+1);
	if(a[poz]==1 && a[poz+2]==3 && poz+4<=k)
		return perla_c(poz+4);
	return false;
}
bool perla_c(int poz)
{
	if(a[poz]==2 && poz==k && nrc==0)
		return 1;
	if(a[poz]==2)
	{
		nrc--;
		return perla_c(poz+1);
	}
	if(a[poz]==3)
	{
		nrc++;
		return perla_b(poz+1);
	}
	if(a[poz]==1 && a[poz+1]==2)
		return perla_a(poz+2);
	return false;
}
int main()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	scanf("%d",&T);
	for(;T;T--)
	{
		scanf("%d",&k);
		for(int i=1;i<=k;i++)
			scanf("%d",&a[i]);
		if(perla_a(1))
		{
			printf("1\n");
			continue;
		}
		nrc=0;
		if(perla_b(1))
		{
			printf("1\n");
			continue;
		}
		nrc=0;
		if(perla_c(1))
		{
			printf("1\n");
			continue;
		}
		nrc=0;
		printf("0\n");
	}
	return 0;
}