#include<fstream>
using namespace std;
ofstream g("perle.out");

int i,j,n,m,a[10002],l;
int rez2(int);
int rez3(int);
int rez2(int i)
{
	while(a[i]==2&&i<=m)
		i++;
		if(a[i]==1&&a[i+2]==3)
			return rez3(i+4);
		else
			return 0;
}
int rez3(int i)
{
	if((a[i]==2&&i==m)||(a[i]==1&&a[i+1]==2&&i+2==m))
		return 1;
	else
		if((i==m&&a[i]!=2)||(i+2==m&&((a[i]!=1||a[i+1]!=2))))
		return 0;
				else
					if(a[i]==3)
					{
						int x=rez2(i+1);
						if(x!=0)
							return rez3(i+1);
						else
							return 0;
					}
}
int main()
{
	ifstream f("perle.in");
	f>>n;
	while(n--)
	{
		f>>m;
		for(i=1;i<=m;i++)
			f>>a[i];
		if(m==1||(a[1]==1&&a[2]==2&&m==3))
			g<<1<<"\n";
		else
		if(m==2||(m==3&&(a[1]!=1||a[2]!=2)))
			g<<0<<"\n";
		else
		{
			if(a[1]==2||a[1]==1)
				{if(rez2(1)!=0)
					g<<1<<"\n";
				else
				g<<0<<"\n";}
			else
				if(a[1]==3)
				{
					if(rez3(1)!=0)
						g<<1<<"\n";
					else
						g<<0<<"\n";
				}
		}
	}
	return 0;
}