#include <stdio.h>
#include <string.h>

int N,T,i,ok,ind;
int v[10001];

inline void B();
inline void C();

inline void B()
{
	if(!ok||ind>N) return;

	if(v[ind]==1)
	{
		if(v[ind+2]!=3)
		{
			ok=0;
			return;
		}
		ind+=4;
		C();
	}
	else
	if(v[ind]==2)
	{
		ind++;
		B();
	}
	else
	if(v[ind]==3)
	{
		ok=0;
		return;
	}

	if(!ok||ind>N) return;
}

inline void C()
{
	if(!ok||ind>N) return;

	if(v[ind]==1&&ind+2==N)
	{
		if(v[ind+1]!=2)
		{
			ok=0;
			return;
		}
		if(ind+2!=N)
		{
			ok=0;
			return;
		}
	}
	else
	if(v[ind]==2)
	{
		if(ind!=N)
		{
			ok=0;
			return;
		}
	}
	else
	if(v[ind]==3)
	{
		ind++;
		B();
		ind++;
		C();
	}

	if(!ok||ind>N) return;
}

int main()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);

	scanf("%d",&T);

	for(;T>0;T--)
	{
		scanf("%d",&N);

		for(i=0;i<N;i++) scanf("%d",&v[i]);

		if(N==1) printf("1\n");
		else
		if(N==2) printf("0\n");
		else
		if(N==3)
		{
			if(v[0]!=1) printf("0\n");
			else
			if(v[1]!=2) printf("0\n");
			else
			printf("1\n");
		}
		else
		{
			ind=1;
			ok=1;
			N--;

			if(v[0]==1) B();
			else
			if(v[0]==2) B();
			else
			if(v[0]==3) C();

			if(ok) printf("1\n");
			else printf("0\n");
		}
	}

	return 0;
}