#include <stdio.h>
#define Nmax 10001

int T;
int p[Nmax], i, n, nr;

int B();
int C();

int B()
{
	if (p[i]==2)
	{
		i++;
		return B();
	}
	else if (p[i]==1)
	{
		if (p[i+2]==3) { i+=4; return C(); }
		else return 0;
	}
	else return 0;
}

int C()
{
	if (p[i]==2 && (i==n || nr)) return 1;
	else if (p[i]==1 && p[i+1]==2 && (i+2==n||nr)) {i+=2; return 1; }
	else if (p[i]==3)
	{
		nr++;
		i++; int a=B();
		nr--;
		i++; int b=C();
		return a&&b;
	}
	else return 0;
}

int main()
{
	freopen("perle.in", "r",stdin);
	freopen("perle.out", "w", stdout);
	scanf("%d\n", &T);
	for (; T; T--)
	{
		scanf("%d ", &n); for (i=1; i<=n; i++) scanf("%d ", &p[i]);
		i=1;
		if (n==1) { printf("1\n"); p[1]=0; continue; }
		if (p[1]==1)
			if (n==3) printf("%d\n", C());
			else printf("%d\n", B());
		else if (p[1]==2) printf("%d\n", B());
		else { printf("%d\n", C()); }
		for (i=1; i<=n; i++) p[i]=0;
	}
	return 0;
}