#include<cstdio>
#include<deque>
#include<string>
#define NMax 11
#define LMax 10002
using namespace std;
FILE *f=fopen("perle.in","r");
FILE *g=fopen("perle.out","w");
int n,L,ok;
int Q[LMax],q[LMax],l;
void RecB(int poz);
void RecC(int poz);

void RecB(int poz)
{int i;
for(i=l;i>=poz;i--)
	q[i+1]=q[i];
l++;
q[poz]=2;q[poz+1]=5;
if(Q[poz]==q[poz] && l<=L)	
	RecB(poz+1);
if(ok==0)
{
for(i=l;i>=poz+1;i--)
	q[i+3]=q[i];
q[poz]=1; q[poz+1]=4; q[poz+2]=3; q[poz+3]=4; q[poz+4]=6;
l+=3;
if(Q[poz]==q[poz] && l<=L)
	RecC(poz+4);
}
}

void RecC(int poz)
{int i,aux=poz;
q[poz]=2;
if(Q[poz]==q[poz] || q[poz]==4)
	{while(q[aux]<5 && aux<=l)aux++;
	if(q[aux]==5) RecB(aux);
	else
		if(q[aux]==6) RecC(aux);
	else if(aux-1==l && l==L){ok=1;return;}
		else return;
	}
if(ok==0)
{for(i=l;i>=poz;i--)
	q[i+2]=q[i];
q[poz]=3; q[poz+1]=5; q[poz+2]=6;
l+=2;
if(q[poz]==Q[poz] && l<=L)
	RecB(poz+1);
}
if(ok==0)
{aux=poz;
q[poz]=1; q[poz+1]=2; q[poz+2]=4;
if((Q[poz]==q[poz] || q[poz]==4)&&l<=L)
{
	while(q[aux]<5 && aux<=l)aux++;
	if(q[aux]==5)RecB(aux);
	else
		if(q[aux]==6)RecC(aux);
	else if(aux-1==l && l==L){ok=1; return;}
	else return;
}
}
}

void Solve()
{int i,j;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
{
	fscanf(f,"%d",&L);
	for(j=1;j<=L;j++)
	{	fscanf(f,"%d",&Q[j]);}
	if(L==1)fprintf(g,"1\n");
	else{q[1]=5;ok=0;l=1;
		RecB(1);
		if(ok==1)fprintf(g,"1\n");
		
	else{q[1]=6;ok=0;l=1;
		RecC(1);
		if(ok==1)fprintf(g,"1\n");
		
	else fprintf(g,"0\n");
	}
	}
	
}
}

int main()
{
Solve();
return 0;
}