#include<fstream>
using namespace std;
ofstream g("perle.out");
int n,i,j,ok,a[10005],lg,sol[10005],l,cc,x;
int transb(int);
int transc(int);
int transb(int i)
{
  while(i<=lg&&a[i]==2)
        i++;
        if(a[i]==1&&a[i+2]==3)
            return transc(i+4);
    else
        return 0;
		  
   
}

int transc(int i)
{
	int k;
	if(a[i]==2)
		return i;
	else
		if(a[i]==1&&a[i+1]==2)
			return i+2;
	
			else
				if(a[i]==3)
				{
					k=transb(i+1);
					if(k)
						return transc(k+1);
					else
						return 0;
				}
		/*if(a[i]==3&&i<=lg-5)
		{
			i++;
			while (a[i]=='2'&&i<lg-4)
			i++;
			if(i==lg)
				return 0;
			else
				if(i==lg-2&&a[i]==1&&a[i+1]==2)
					return lg;
					else
						if(lg-i>=4&&a[i]==1&&a[i+2]==3)
								return transc(i+5);
						
		}*/
		else
				return 0;

		
}
						
					
			
			

int main()
{
	ifstream f("perle.in");
	f>>n;
	for(x=1;x<=n;x++)
	{
		ok=0;
		f>>lg;
		for(i=1;i<=lg;i++)
			f>>a[i];
		if(lg==1||(lg==3&&a[1]==1&&a[2]==2))
			ok=1;
		else
			if(lg==2||lg==3)
				ok=0;
		else
		{
			if(transb(1)==lg||transc(1)==lg)
				ok=1;
			else
				ok=0;
			
		}
		g<<ok<<"\n";
	}
	return 0;
}