#include <fstream.h>

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

int b(int k);
int c(int k);

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; }
			if (init=='B') b(0);
			else if (init=='C') c(0);
			if (ok) g<<"1\n"; else g<<"0\n";

		}
	g.close();
	return 0;
}

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

int c(int poz)
{
	if (poz+1<nr && p[poz]==3) {b(poz+1); c(poz+1);}
	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 ok=0;
	return 0;

}