#include<fstream>
using namespace std;
FILE *g=fopen("perle.out","w");

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(i==l && a[i]==2)
		return i;
	else
		if(a[i]==1&&a[i+1]==2)
			return i+2;
		else
			if(a[i]==3)
			{
				int x=rez2(i+1);
				if(x!=0)
					return rez3(x+1);
				else
					return 0;
			}
			else
				return 0;
}
int main()
{
	FILE *f=fopen("perle.in","r");
	fscanf(f,"%d",&n);
	while(n--)
	{
		fscanf(f,"%d",&m);
		for(i=1;i<=m;i++)
			fscanf(f,"%d",&a[i]);
		if(m==1||(a[1]==1&&a[2]==2&&m==3))
			fprintf(g,"1\n");
		else
		if(m==2||(m==3&&(a[1]!=1||a[2]!=2)))
			fprintf(g,"0\n");
		else
		{
			if(a[1]==2||a[1]==1)
				{if(rez2(1)==m)
					fprintf(g,"1\n");
				else
					fprintf(g,"0\n");
				}
			else
				if(a[1]==3)
				{
					if(rez3(1)==m)
						fprintf(g,"1\n");
					else
						fprintf(g,"0\n");
				}
		}
	}
	return 0;
}