#include<stdio.h>

const char in[]="perle.in";
const char out[]="perle.out";
const int N=10005;

int n, v[N];

int A();
int B(int i);
int C(int i);

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		int T, j;
		for(scanf("%d", &T);T--;)
		{
			scanf("%d", &n);
			for(j=1;j<=n;++j)
				scanf("%d", &v[j]);
			printf("%d\n",A()); 
		}
	return 0;
}

int A()
	{
		if(n == 1)return 1;
		if(n == 2)return 0;
		if(v[1] == 3) return C(1);
		return B(1);
}

int B(int i)
	{
		if(v[i] == 2) return B(i+1);
		if(v[i] == 1 && v[i+2] == 3)return C(i+4);
		return C(i+1);
}

int C(int i)
	{
		if(v[i] == 2 && i == n)return 1;
		if(v[i] == 2) return C(i+1);
		if(v[i] == 3) return B(i+1);
		if(v[i] == 1 && v[i+1] == 2 && i+2 == n)return 1;
		if(v[i] == 1 && v[i+1] == 2)return C(i+3);
		return 0;
}