#include <stdio.h>
#include <string.h>
#define NMax 10010

const char IN[]="perle.in",OUT[]="perle.out";

int Tes;
int N,A[NMax];
int l;
bool b(),c();

bool c()
{
	if (A[l]==2) {++l;return true;}
	if (A[l]==1 && A[l+1]==2) {l+=3;return true;}
	if (A[l]==3) {++l;b();return c();}
	return false;
}

bool b()
{
	if (A[l]==2) {++l; return b();}
	if (N-l+1>=4 && A[l]==1 && A[l+2]==3) {l+=4;return c();}
	return false;
}

int main()
{
	int i;bool sol;
	freopen(IN,"r",stdin);
	scanf("%d",&Tes);

	freopen(OUT,"w",stdout);
	while (Tes--)
	{
		scanf("%d",&N);
		memset(A,0,sizeof(A));
		for (i=1;i<=N;++i) scanf("%d",A+i);

		l=1;sol=false;
		sol|=b() && l>=N;
		l=1;sol|=c() && l>=N;
		sol|=(N==1);
		printf("%d\n",sol);
	}
	fclose(stdout);
	return 0;
}