# include <fstream>
# define DIM 10003
# define max MAX
//       A -> 1   |     2 | 3
//       B -> 2B  | 1A3AC
//       C -> 2   |   3BC | 12A
using namespace std;
int n, v[DIM], l, rez, x[DIM], max;

void pune (int k)
{
	if (max>l)return;
	if (k==l+1 && max==l)
	{
		rez=1;
		return;
	}
	if (x[k]==v[k])
		pune(k+1);
	else
		if (x[k]==4)
		{
			x[k]=v[k];
			pune(k+1);
		}
		else if (x[k]==5)
			{
				if (v[k]==1)
				{
					for(int i=max;i>k;--i)
						x[i+4]=x[i];
					max+=4;
					x[k]=1;x[k+1]=4;x[k+2]=3;x[k+3]=4;x[k+4]=6;
					pune(k+1);
				}
				else
					if (v[k]==2)
					{	
						for(int i=max;i>k;--i)
							x[i+1]=x[i];
						++max;
						x[k]=2;x[k+1]=5;
						pune(k+1);
					}
			}
//       C -> 2   |   3BC | 12A
		else if (x[k]==6)
		{
			if (v[k]==1)
			{
				for(int i=max;i>k;--i)
					x[i+2]=x[i];
				max+=2;
				x[k]=1;x[k+1]=2;x[k+2]=4;
				pune(k+1);
			}
			else if (v[k]==2)
			{
				x[k]=2;
				pune(k+1);
			}
			else if (v[k]==3)
			{
				for(int i=max;i>k;--i)
					x[i+2]=x[i];
				max+=2;
				x[k]=3;x[k+1]=5;x[k+2]=6;
				pune(k+1);
			}
		}
}
	

int main ()
{
	ifstream fin ("perle.in");
	ofstream fout ("perle.out");
	fin>>n;
	for (;n--;)
	{
		fin>>l;
		rez=0;
		for(int i=1;i<=l;i++)fin>>v[i];
		for(int i=4;i<7 && !rez;++i)
		{
			x[1]=i;
			max=1;
			pune(1);
		}
		fout<<rez<<"\n";
	}
	return 0;
}