#include<stdio.h>

char sir[10240];
struct entry{int val; entry *adr;} *start, *stop, *p;
int verifica(int n)
{
	int count=0;
	entry *k, *t, *l;
	p=start;
	while(p && (count<=n+1))
	{   
		++count;
		if ((p->val)<4) 
		{	
			if (p->val==sir[count]){ p=p->adr; continue;}
			else return 0;
		}
		if (p->val==4) {p->val=sir[count]; p=p->adr; continue;}
		if ((p->val)==5)
		{
			if (sir[count]==3) return 0;
			if (sir[count]==2)
			{
				p->val=2;
				k=new entry;
				k->val=5;
				k->adr=p->adr;
				p->adr=k;
				p=p->adr;
				continue;
			}
			if (sir[count]==1)
			{
				p->val=1;
				k=new entry;
				l=k;
				k->val=4;
				t=k;
				k=new entry;
				t->adr=k;
				k->val=3;
				t=k;
				k=new entry;
				t->adr=k;
				k->val=4;
				t=k;
				k=new entry;
				t->adr=k;
				k->val=6;
				k->adr=p->adr;
				p->adr=l;
				p=p->adr;
				continue;
			}
		}
		
		if ((p->val)==6)
		{
			if (sir[count]==2){p->val=2; p=p->adr; continue;}
			if (sir[count]==1)
			{
				p->val=1;
				k=new entry;
				t=k;
				k->val=2;
				k=new entry;
				t->adr=k;
				k->val=4;
				k->adr=p->adr;
				p->adr=t;
				p=p->adr;
				continue;
			}
			if (sir[count]==3)
			{
				p->val=3;
				k=new entry;
				t=k;
				k->val=5;
				k=new entry;
				t->adr=k;
				k->val=6;
				k->adr=p->adr;
				p->adr=t;
				p=p->adr;
				continue;				
			}
		}
	}
	if (count<n) return 0;
	if (count>n) return 0;
	return 1;
}

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

	int n, numar, i;
    scanf("%d", &numar);
	while (numar)
	{
		--numar;
		scanf("%d", &n);
		for (i=1; i<=n; i++)
			scanf("%d", &sir[i]);

		if (n==1) {printf("1\n"); continue;}
		if (n==2) {printf("0\n"); continue;}
		if (n==3) if ((sir[1]==1) && (sir[2]==2)) {printf("1\n"); continue;}
				  else {printf("0\n"); continue;}
		if (n==4) {printf("0\n"); continue;}
		
		if (sir[1]==1) 
		{
			p=new entry;
			p->adr=NULL;
			p->val=1;
			start=p;
			stop=p;
			p=new entry;
			p->adr=NULL;
			p->val=4;
			stop->adr=p;
			stop=stop->adr;
			p=new entry;
			p->adr=NULL;
			p->val=3;
			stop->adr=p;
			stop=stop->adr;
			p=new entry;
			p->adr=NULL;
			p->val=4;
			stop->adr=p;
			stop=stop->adr;
			p=new entry;
			p->adr=NULL;
			p->val=6;
			stop->adr=p;
			stop=stop->adr;
			printf("%d\n", verifica(n) ); 
			continue;
		} 
		if (sir[1]==2) 
		{
			p=new entry;
			p->adr=NULL;
			p->val=2;
			start=p;
			stop=p;
			p=new entry;
			p->adr=NULL;
			p->val=5;
			stop->adr=p;
			stop=stop->adr;
			printf("%d\n", verifica(n) ); 
			continue;
		}
		if (sir[1]==3) 
		{
			p=new entry;
			p->adr=NULL;
			p->val=3;
			start=p;
			stop=p;
			p=new entry;
			p->adr=NULL;
			p->val=5;
			stop->adr=p;
			stop=stop->adr;
			p=new entry;
			p->adr=NULL;
			p->val=6;
			stop->adr=p;
			stop=stop->adr;
			printf("%d\n", verifica(n) ); 
			continue;
		}
    }
	return 0;
}