#include <fstream>
#include <string.h>

std::ifstream f1("in.txt");
std::ofstream f2("out.txt");

int rez(int r[10000], int ind, int sir[10000], int poz, int l);

int main()
{
	int r[10000], sir[10000], corect, n, l, i, j;
  f1>>n;
	for (i=0; i<n; i++)
	{
		f1>>l;
		for (j=0; j<l; j++)
		  f1>>sir[j];
  	if (l==1)
	  	corect=1;
  	else
 	  	if (l==2)
  	  	corect=0;
    	else
	    	if ((l==3)&&((sir[0]!=1)||(sir[1]!=2)))
        	corect=0;
			  else
				  if (l==3)
					  corect=1;
  	      else
	  		  {
		  			if (sir[0]==1)
			  			r[0]=5;
				  	else
					  	if (sir[0]==2)
						  	r[0]=5;
  					  else
	  						if (sir[0]==3)
		  						r[0]=6;
			  		corect=rez(r, 0, sir, 0, l-1);
				  }//else
		f2<<corect<<"\n";
	}//for i
	return 0;
}//main

int rez(int r[10000], int ind, int sir[10000], int poz, int l)
{
	int i;
	if ((poz>l)&&(ind==-1))
		return 1;
	else
		if ((poz>l)||(ind==-1))
			return 0;
	  else
    	if ((r[0]==4)||(r[0]==sir[poz])||((r[0]==6)&&(sir[poz]==2)))
    	{
  	  	poz++;
	  	  for (i=0; i<=ind-1; i++)
	   	    r[i]=r[i+1];
	   		ind--;
	   		return rez(r, ind, sir, poz, l);
	   	}//if
	   	else
	   		if ((l-poz+1)==1)
	   			return 0;
	   		else
	    			if (r[0]==5)
	     		{
	   	  		if (sir[poz]==2)
	   		  	{
	   			  	poz++;
	   				  return rez(r, ind, sir, poz, l);
	    				}//if
	     			else
	   	  			if (sir[poz]==1)
	   		  		{
	   			  		poz++;
	   				  	for (i=ind; i>=1; i--)
	   					  	r[i+3]=r[i];
	    					r[0]=4;
	     					r[1]=3;
	   	  				r[2]=4;
	   		  			r[3]=6;
	   			  		ind+=3;
	   				  	return rez(r, ind, sir, poz, l);
	    					}//if
	       		  else
	   	  				return 0;
	    			}//if
	     		else
	   	  	{
	   		  	if (r[0]==6)
	   			  {
	    					if (sir[poz]==3)
	     				{
	   	  				poz++;
	   		  			ind++;
	   			  		for (i=ind; i>=1; i--)
	   				  		r[i]=r[i-1];
	   					  r[0]=5;
	   						return rez(r, ind, sir, poz, l);
	    					}//if
	     			  else
	   	  			  if (sir[poz]==1)
	   						{
                  poz++;
	   	  			  	for (i=ind; i>=1; i--)
	   		  			  	r[i+1]=r[i];
		   		  			r[0]=2;
		   			  	  r[1]=4;
		   					  ind+=1;	
		   						return rez(r, ind, sir, poz, l);
		   					}//if
		   					else
		   						return 0;
		   	  	}//if
		   	  }//else
	return 0;
}//rez