#include<fstream>
#define dmax 11000
using namespace std;

int n,a[dmax],lg,s[dmax],gasit;

void recursiv(int poz)
{
 int i;
	
 if (poz>lg)
	 {
	  if (lg==n)
		 gasit=1;
	 } else
	 {
	  if (s[poz]==4)
		  {
		   s[poz]=a[poz]; 
		   recursiv(poz+1);
		  } else
		  if (s[poz]==5)
			 {
			  if (a[poz]==1)
				  {
				   for (i=lg+1; i<=lg+4; i++)
					   s[i]=s[i-4];
				   s[poz]=1; s[poz+1]=4; s[poz+2]=3; s[poz+3]=4; s[poz+4]=6;
				   lg+=4;
				   recursiv(poz+1);
				  } else
				  if (a[poz]==2)
					  {
					   for (i=lg+1; i<=lg+1; i++)
						   s[i]=s[i-1];
					   s[poz]=2; s[poz+1]=5;
					   lg+=1;
					   recursiv(poz+1);
					  }
			 } else
			 if (s[poz]==6)
				 {
				  if (a[poz]==1)
					  {
					   for (i=lg+1; i<=lg+2; i++)
						   s[i]=s[i-2];
					   s[poz]=1; s[poz+1]=2; s[poz+2]=4;
					   lg+=2;
					   recursiv(poz+1);
					  } else
					  if (a[poz]==2)
						  {
						   s[poz]=2;
						   recursiv(poz+1);
						  } else
						  if (a[poz]==3)
							 {	
							  for (i=lg+1; i<=lg+2; i++)
								   s[i]=s[i-2];
							  s[poz]=3; s[poz+1]=5; s[poz+2]=6;
							  lg+=2;
							  recursiv(poz+1);
							 }
				 } else
				 if (s[poz]==a[poz])
					 recursiv(poz+1);
	 }
}


int solve()
{
	
 if (n==1)
	 return 1; else
	 {
	  gasit=0;
	  s[1]=4; lg=1; /*incerc cu perla de tip A*/
	  recursiv(1);
	  if (gasit==0)
		  {
		   s[1]=5; lg=1; /*incerc cu perla de tip B*/
		   recursiv(1);
		  }
	  if (gasit==0)
		  {
		   s[1]=6; lg=1; /*incerc cu perla de tip C*/
		   recursiv(1);
		  }
	  return gasit;
	 }
}


int main()
{
 int t,i,j;
	
 ifstream fin("perle.in");
 ofstream fout("perle.out");
 
 fin>>t;
 for (j=1; j<=t; j++)
	 {
	  fin>>n;
	  for (i=1; i<=n; i++)
		  fin>>a[i];
	  
	  fout<<solve()<<'\n';
	 }
	
 fin.close();
 fout.close(); 
 
 return 0;
}