#include<stdio.h>
char a1[1]={'1'},a2[1]={'2'},a3[1]={'3'};
char b1[2]={'2','B'},b2[5]={'1','A','3','A','C'};
char c1[1]={'2'},c2[3]={'3','B','C'},c3[3]={'1','2','A'};
int i,j,n,l,l2,rasp=0;
int v[10010];
char stiva[10010];
void incearca(int in,int in2)
{

	int aux=1;
	while(aux&&in>0)
	{
		if(v[in]==int (stiva[in2])-'0' ||stiva[in2]=='A')
			in--,in2--;
		else
			aux=0;
	}

	if(in==0&&in2==0)
	{
		rasp=1;
		return;
	}
	if(in==0)
		return;

	if(v[in]==1)
	{
		if(stiva[in2]=='C')
		{

			in2--;
			stiva[in2+1]='A';
			stiva[in2+2]='2';
			stiva[in2+3]='1';
			in2+=3;
			incearca(in,in2);

		}
		if(stiva[in2]=='B')
		{
			in2--;
			stiva[in2+1]='C';
			stiva[in2+2]='A';
			stiva[in2+3]='3';
			stiva[in2+4]='A';
			stiva[in2+5]='1';
			in2+=5;
			incearca(in,in2);

		}
		if(stiva[in2]=='A')
		{
			stiva[in2]='1';

			incearca(in,in2);
			}

	}
	if(v[in]==2)
	{
		if(stiva[in2]=='C')
		{

			stiva[in2]='2';

			incearca(in,in2);

		}
		if(stiva[in2]=='B')
		{
			in2--;
			stiva[in2+1]='B';
			stiva[in2+2]='2';
			in2+=2;
			incearca(in,in2);

		}
		if(stiva[in2]=='A')
		{

			stiva[in2]='2';

			incearca(in,in2);

		}
	}
	if(v[in]==3)
	{
		if(stiva[in2]=='C')
		{
			in2--;
			stiva[in2+1]='C';
			stiva[in2+2]='B';
			stiva[in2+3]='3';
			in2+=3;
			incearca(in,in2);

		}
		if(stiva[in2]=='A')
		{
			stiva[in2]='3';

			incearca(in,in2);

		}
	}


}
int main()
{


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

	scanf("%d",&n);

	for(;n>0;n--)
	{
		rasp=0;
		l2=0;
		scanf("%d",&l);
		for(i=1;i<=10010;i++)
			stiva[i]='0';

		for(i=l;i>0;i--)
			scanf("%d",&v[i]);

		stiva[1]='B';
		incearca(l,1);
		if(rasp==0)
		{
			stiva[1]='C';
			incearca(l,1);
		}
		if(rasp==0)
		{
			stiva[1]='A';
			incearca(l,1);
		}
		printf("%d\n",rasp);
	}

	return 0;
}