#include<iostream>
#include<fstream.h>
#include<string.h>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

int Perla_A();
int Perla_B(int i);
int Perla_C(int i);
int t,lungime,i,j,rez,ok,n;
int v[11000];

int main()
{
	fin>>t;
	for(i=1;i<=t;i++)
	{   
		fin>>n;
		for(j=1;j<=n;j++)
			fin>>v[j];
		ok=Perla_A();
		if(ok!=1)
			ok=0;
		fout<<ok<<"\n"; 
		for(j=1;j<=n;j++)
			v[j]=0;
	}
	return 0;
}

int Perla_A()
{
	if(n==1)
		return 1;
	if(n==2)
		return 0;
	if(v[1]==3)
		return Perla_C(1);
	return Perla_B(1);
}

int Perla_C(int i)
{	
	if(v[i]==2 && i==n)
		return 1;
	if(v[i]==2)
		return Perla_C(i+1);
	if(v[i]==3)
		return Perla_B(i+1);
	if(v[i]==1 && v[i+1]==2 && i+2==n)
		return 1;
	if(v[i]==1 && v[i+1]==2)
		return Perla_C(i+3);
}

int Perla_B(int i)
{
	if(v[i]==2)
		return Perla_B(i+1);
	if(v[i]==1 && v[i+2]==3)
		return Perla_C(i+4);
	return Perla_C(i+1);
}