#include <fstream.h>

int  n, p[10000], nr, ok, poz;

int b();
int c();

int main()
{
	int i, j;
	char init;
	ofstream g("perle.out");
	ifstream f("perle.in");
	f>>n;
	for (i=0; i<n; i++)
		{
			init='\0';
			ok=0;
			f>>nr;
			for (j=0; j<nr; j++)
				f>>p[j];
			if (nr==1) {g<<"1\n"; continue; }
			else if (nr==3 && p[0]==1 && p[1]==2)	init='C';
			else if (nr>1 && p[0]==2) init='B';
			else if (nr>3 && p[0]==1) init='B';
			else if (nr>1 && p[0]==3) init='C';
			if (init=='\0') {g<<"0\n"; continue; }
			poz=0;
			if (init=='B') b();
			else if (init=='C') c();
			if (ok) g<<"1\n"; else g<<"0\n";

		}
	g.close();
	return 0;
}

int b()
{
	if (poz+1<nr && p[poz]==2) {poz++; b();}
	else if (poz+4<nr && p[poz]==1 && p[poz+2]==3) {poz+=4; c(); }
	else ok=0;
	return 0;
}

int c()
{
	if (poz+2<nr && p[poz]==3) {poz++; b(); c();}
	else if (nr-3==poz && p[poz]==1 && p[poz+1]==2) ok= 1;
	else if (poz==nr-1 && p[poz]==2)  ok=1;
	else if (p[poz]==1 && p[poz+1]==2) poz+=3;
	else if (p[poz]==2)  poz++;
	else ok=0;
	return 0;

}