#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int a[10002],b[10002],c[10002];
int n,lung,poz,k=0,l;

int b1()
{
	b[k]=2;
	b[k+1]=20;
	k+=2;
	return 0;
}

int b2()
{
	b[k]=1;
	b[k+1]=10;
	b[k+2]=3;
	b[k+3]=10;
	b[k+4]=30;
	k+=5;
	return 0;
}

int c1()
{
	b[k]=2;
	k++;
	return 0;
}

int c2()
{
	b[k]=3;
	b[k+1]=20;
	b[k+2]=30;
	k+=3;
	return 0;
}

int c3()
{
	b[k]=1;
	b[k+1]=2;
	b[k+2]=10;
	k+=3;
	return 0;
}

int save()
{
	int ch=poz+1;
	for (l=0;b[l]!=0;l++)
	{
		c[l]=b[ch];
		ch++;
	}
	return 0;
}

int paste()
{
	for (int i=0;c[i]!=0;i++)
	{
		b[k]=c[i];
		k++;
	}
	return 0;
}

int sir()
{
	poz=0;
	int ok=1;
	while (ok && a[poz]!=0)
	{
		poz++;
		if (b[poz]==10)
			b[poz]=a[poz];
		if (b[poz]==20)
		{
			if (a[poz]==1)
			{
				save();
				k-=l;
				b2();
				paste();
				memset(c,0,10002);
			}
			else
			{
				if (a[poz]==2)
				{
					save();
					k-=l;
					b1();
					paste();
					memset(c,0,10002);
				}
				else if (a[poz]==3)
						ok=0;
			}
		}
		if (b[poz]==30)
		{
			if (a[poz]==1)
			{
				save();
				k-=l;
				c3();
				paste();
				memset(c,0,10002);
			}
			else
			{
				if (a[poz]==2)
				{
					save();
					k-=l;
					c1();
					paste();
					memset(c,0,10002);
				}
				else if (a[poz]==3)
				{
					save();
					k-=l;
					c2();
					paste();
					memset(c,0,10002);
				}
			}
		}
		if (b[poz]!=a[poz])
			ok=0;
		if (poz!=k)
			ok=1;
	}
	return ok;
}

int main()
{
	ifstream f("perle.in");
	ofstream g("perle.out");
	int nrperle;
	f>>nrperle;
	for (int m=1;m<=nrperle;m++)
	{
		k=1;
		memset(a,0,10002);
		memset(b,0,10002);
		f>>n; //lungimea sirului
		for (int i=0;i<n;i++)//se citeste sirul
				f>>a[i];
		if (n==1)
			g<<1<<endl;
		else if (n==2)
				g<<0<<endl;
		else 
		{
			if (n==3)
			{
				if ((a[0]==1 && a[1]==2 && a[2]==1)||(a[0]==1 && a[1]==2 && a[2]==2)||(a[0]==1 && a[1]==2 && a[2]==3))
					g<<1<<endl;
				else g<<0<<endl;
			}
			else
			{
				if (a[0]==2)
					b1();
				if (a[0]==1)
					b2();
				if (a[0]==3)
					c2();
				if (sir())
					g<<1<<endl;
				else g<<0<<endl;
			}
		}
	}
	f.close();
	g.close();
	return 0;
}