#include<stdio.h>
#define infile "perle.in"
#define outfile "perle.out"
#define lmax 10*1000+1
char v[lmax]; //vectorul in care citim
int l; //lungimea sirului
int t; //numarul de teste

void citire(char v[lmax], int *l)
	{
	int i;
	scanf("%d",l); //citim lungimea sirului
	for(i=1;i<=*l;i++) //luam fiecare element al sirului in parte
		scanf("%d",&v[i]); //il salvam in vector
	}

//muta intervalul p->q cu x pozitii spre dreapta
void mutare_sir(char v[], int p, int q, int x)
	{
	while(q>=p) //cat timp nu am copiat toate elementele intervalului
		{
		v[q+x]=v[q]; //mutam ultimul element din interval cu x pozitii la dreapta
		q--; //scadem capatul intervalului, adica elementul copiat
		}
	}

//verifica daca se poate reface sirul pornind de la oricare perla (1-DA, 0-NU)
int se_poate(char v[lmax], int l)
	{
	char w[lmax]; //vectorul in care incercam sa refacem codul
	int i; //variabila cu care vom parcurge vectorul in care refacem sirul
	int j; //variabila care retine extremitatea dreapta a vectorului in care refacem sirul
	if(l==1) return 1; //se poate reface sirul pornind de la perla A
	if(l==2) return 0; //nu se paote reface sirul prnind de la oricare perla magina
	//avem lungimea mai mare sau egala cu 3 caractere
	
	//selectam perla de la care incepem
	if(v[1]=='3' || (v[1]=='1' && v[2]=='2' && l=='3')) w[1]='C'; //e posibil sa se poata doar pornind de la perla magica c
	else if(v[1]=='2' || v[1]=='1') w[1]='B'; //e posibil sa se paota doar pornind de la perla magica B
	else return 0; //inseamna ca nu se poate reface sirul
	
	//incercam refacerea sirului pornind de la perla magica deja gasita
	for(i=j=1;i<=l;i++,j++) //incercam refacerea sirului trecand pe la fiecare pozitie in parte
		{
		if(w[i]=='A') //daca avem perla A
			w[i]=v[i]; //putem pune orice din sirul initial
		else if(w[i]=='B') //daca avem perla magica B
			{
			if(v[i]=='2') //o schimbam in 2B
				{
				mutare_sir(w,i+1,j,1); //mutam spre dreapta subsirul i+1->j cu o pozitie
				w[i]=v[i]; //adica 2
				w[++i]='B';
				j++; //creste si extremitatea sirului cu 1
				}
			else if(v[i]=='1' && v[i+2]=='3') //o schimbam in 1A3AC
				{
				mutare_sir(w,i+1,j,4); //mutam spre dreapta sirul i+1->j cu 4 pozitii
				w[i]=v[i]; //adica 1
				w[++i]=v[i]; //adica A transformat
				w[++i]=v[i]; //adica 3
				w[++i]=v[i]; //adica A transformat
				w[++i]='C';
				j+=4; //creste si extremitatea sirului cu 4
				}
			else return 0; //nu se paote obtine sirul
			}
		else if(w[i]=='C') //avem o perla magica de tip C
			{
			if(v[i]=='2') w[i]=v[i]; //primeste transformarea b->2
			else if(v[i]=='3') //se transforma in 3BC
				{
				mutare_sir(w,i+1,j,2); //mutam spre dreapta sirul i+1->j cu 2 pozitii
				w[i]=v[i]; //adica 3
				w[++i]='B';
				w[++i]='C';
				j+=2; //crestem si extremitatea sirului cu 2
				}
			else if(v[i]=='1' && v[i+1]=='2') //se transforma in 12A
				{
				mutare_sir(w,i+1,j,2); //mutam spre dreapta sirul i+1->j cu 2 pozitii
				w[i]=v[i]; //adica 1
				w[++i]=v[i]; //adica 2
				w[++i]=v[i]; //adica a transformat
				}
			else return 0; //nu se poate obtine sirul
			}
		}
	return 1; //daca s-a ajuns aici inseamna ca sirul paote fi obtinut
	}

int main()
{
//deschidem fisiere
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

scanf("%d",&t); //citim numarul de teste
while(t) //cat timp mai avem de verificat siruri
	{
	citire(v,&l); //citim lungimea sirului si sirul
	printf("%d\n",se_poate(v,l)); //se scrie raspunsul primit de functie
	t--; //am terminat de facut testul
	}

//inchidem fisiere
fclose(stdin);
fclose(stdout);
return 0;
}