#include<fstream>
using namespace std;

int n,li;
int sir[10010],tr[10010];

int solution()
{int i,ok,k,j,ok1,ok2;
ok2=1;
if(li==1)                          //Perlele de tip A = -1
  {return 1; ok2=0;}                       //Perlele de tip B = -2
else                               //Perlele de tip C = -3
  {if(li==2)
	  {return 0; ok2=0;}
   else
     {tr[1]=sir[1];
      if(tr[1]==1)                  //daca sirul incepe cu 1 sunt posibile situatiile B2 sau C3 
	    {if(li==3)                  //Verificarea daca este posibila inlocuirea cu C3
            {tr[2]=2;
			 tr[3]=sir[3];}
		 else
			{tr[2]=-1;              //Daca C3 nu este posibila singura varianta ramasa este B2
		     tr[3]=3;
			 tr[4]=-1;
			 tr[5]=-3;
			 ok=1;  k=5;
			 if(k>li)                    //Verific daca lungimea sirului meu nu este mai mare decat lungimea 
				 {return 0;   ok2=0;}         //sirului dat
			 else
			   while(ok==1)
			         {ok=0;             //Presupun ca elimin toate perlele magice         
				      for(i=1;i<=k;i++)
				         if(tr[i]<0)          //Gasesc perla magica                      
						   {ok1=1;              //O variabila care tine evidenta daca a inlocuit deja perla magica
							if((tr[i]==-1)&&(ok1==1))        //Verific daca este tip A
						      {if(sir[i]==1)     //Caut si inlocuiesc cu perlele normale din sirul original
								  {tr[i]=1;
							       ok1=0;}
							   if(sir[i]==2)
								  {tr[i]=2;
							       ok1=0;}
							   if(sir[i]==3)
								  {tr[i]=3;
							       ok1=0;}
							  }
							if((tr[i]==-2)&&(ok1==1))        //Verific daca este tip B
							  {ok=1;             //Sigur inlocuiesc cu perla magica
							   if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
							     {tr[i]=2; ok1=0;      //inlocuiesc cu perla tip 2 
					              for(j=k;j>i;j--)    //mut tot sirul cu o unitate in spate pt a putea pune 
									  tr[j+1]=tr[j];   //perla magica de tip B
								  tr[++i]=-2;
								  k+=1;
								  i-=1;}
							   if((sir[i]==1)&&(ok1==1))      //Verific daca sirul incepe cu perla normala de tip 1
							     {tr[i]=1; ok1=0;               //inlocuiesc cu perla tip 1 
							      for(j=k;j>i;j--)          //mut tot sirul cu 4 unitati in spate pt a putea pune
									  tr[j+4]=tr[j];        //restul transformarii : A3AC
								  tr[++i]=-1;              //Se completeaza cu restul transformarii
								  tr[++i]=3;
								  tr[++i]=-1;
								  tr[++i]=-3;
								  k+=4; i-=4;
								 }
							   if((sir[i]==3)&&(ok1==1))
								   {return 0;  ok2=0;
									break;}
							  }
							if((tr[i]==-3)&&(ok1==1))        //Verific daca este tip C
							  {if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
							     {tr[i]=2;                   //Inlocuiesc cu tip 2
							      ok1=0;}
							   if((sir[i]==3)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 3
							     {ok=1;                       //Pun 2 perle magice
								  tr[i]=3;
								  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
								     tr[j+2]=tr[j];          //restul transformarii : BC
								  tr[++i]=-2;                //Se completeaza cu restul transformarii
								  tr[++i]=-3;
								  k+=2; i-=2;}
							   if((sir[i]==1)&&(ok1==1))
							     {ok=1;                      //Pun perla magica
							      tr[i]=1;
								  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
								     tr[j+2]=tr[j];          //restul transformarii : 2A
								  tr[++i]=2;                //Se completeaza cu restul transformarii
								  tr[++i]=-1;
								  k+=2; i-=2;}
							  }
						   }   						   
					 }
			}
		}
	 if(tr[1]==2)
	   {tr[2]=-2;
        ok=1;  k=2;
		if(k>li)                //Verific daca lungimea sirului meu nu este mai mare decat lungimea 
		  {return 0;     ok2=0;}       //sirului dat
		else
		  while(ok==1)
			   {ok=0;             //Presupun ca elimin toate perlele magice         
				for(i=1;i<=k;i++)
					if(tr[i]<0)          //Gasesc perla magica                      
					  {ok1=1;              //O variabila care tine evidenta daca a inlocuit deja perla magica
					   if((tr[i]==-1)&&(ok1==1))        //Verific daca este tip A
						 {if(sir[i]==1)     //Caut si inlocuiesc cu perlele normale din sirul original
							{tr[i]=1;
							 ok1=0;}
						  if(sir[i]==2)
							{tr[i]=2;
							 ok1=0;}
						  if(sir[i]==3)
							{tr[i]=3;
							 ok1=0;}
						 }
					   if((tr[i]==-2)&&(ok1==1))        //Verific daca este tip B
						 {ok=1;             //Sigur inlocuiesc cu perla magica
						  if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
						    {tr[i]=2; ok1=0;      //inlocuiesc cu perla tip 2 
							 for(j=k;j>i;j--)    //mut tot sirul cu o unitate in spate pt a putea pune 
								 tr[j+1]=tr[j];   //perla magica de tip B
							 tr[++i]=-2;
							 k+=1; i-=1;}
						  if((sir[i]==1)&&(ok1==1))      //Verific daca sirul incepe cu perla normala de tip 1
							{tr[i]=1; ok1=0;               //inlocuiesc cu perla tip 1 
							 for(j=k;j>i;j--)          //mut tot sirul cu 4 unitati in spate pt a putea pune
							    tr[j+4]=tr[j];        //restul transformarii : A3AC
							 tr[++i]=-1;              //Se completeaza cu restul transformarii
							 tr[++i]=3;
							 tr[++i]=-1;
							 tr[++i]=-3;
							 k+=4; i-=4;
							}
						  if((sir[i]==3)&&(ok1==1))
							 {return 0;  ok2=0;
							  break;}
							 }
					   if((tr[i]==-3)&&(ok1==1))        //Verific daca este tip C
						 {if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
							 {tr[i]=2;                   //Inlocuiesc cu tip 2
							  ok1=0;}
							  if((sir[i]==3)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 3
							     {ok=1;                       //Pun 2 perle magice
								  tr[i]=3;
								  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
								     tr[j+2]=tr[j];          //restul transformarii : BC
								  tr[++i]=-2;                //Se completeaza cu restul transformarii
								  tr[++i]=-3;
								  k+=2; i-=2;}
							   if((sir[i]==1)&&(ok1==1))
							     {ok=1;                      //Pun perla magica
							      tr[i]=1;
								  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
								     tr[j+2]=tr[j];          //restul transformarii : 2A
								  tr[++i]=2;                //Se completeaza cu restul transformarii
								  tr[++i]=-1;
								  k+=2; i-=2;}
						 }
					  }
			   }
	   }
	 if(tr[1]==3)
	   {tr[2]=-2;
	    tr[3]=-3;
        ok=1;  k=3;
		if(k>li)                //Verific daca lungimea sirului meu nu este mai mare decat lungimea 
		  {return 0; ok2=0;}           //sirului dat
		else
		  while(ok==1)
			   {ok=0;             //Presupun ca elimin toate perlele magice         
				for(i=1;i<=k;i++)
					if(tr[i]<0)          //Gasesc perla magica                      
					  {ok1=1;              //O variabila care tine evidenta daca a inlocuit deja perla magica
					   if((tr[i]==-1)&&(ok1==1))        //Verific daca este tip A
						 {if(sir[i]==1)     //Caut si inlocuiesc cu perlele normale din sirul original
							{tr[i]=1;
							 ok1=0;}
						  if(sir[i]==2)
							{tr[i]=2;
							 ok1=0;}
						  if(sir[i]==3)
							{tr[i]=3;
							 ok1=0;}
						 }
					   if((tr[i]==-2)&&(ok1==1))        //Verific daca este tip B
						 {ok=1;             //Sigur inlocuiesc cu perla magica
						  if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
						    {tr[i]=2; ok1=0;      //inlocuiesc cu perla tip 2 
							 for(j=k;j>i;j--)    //mut tot sirul cu o unitate in spate pt a putea pune 
								 tr[j+1]=tr[j];   //perla magica de tip B
							 tr[++i]=-2;
							 k+=1; i-=1;}
						  if((sir[i]==1)&&(ok1==1))      //Verific daca sirul incepe cu perla normala de tip 1
							{tr[i]=1; ok1=0;               //inlocuiesc cu perla tip 1 
							 for(j=k;j>i;j--)          //mut tot sirul cu 4 unitati in spate pt a putea pune
							    tr[j+4]=tr[j];        //restul transformarii : A3AC
							 tr[++i]=-1;              //Se completeaza cu restul transformarii
							 tr[++i]=3;
							 tr[++i]=-1;
							 tr[++i]=-3;
							 k+=4; i-=4;
							}
						  if((sir[i]==3)&&(ok1==1))
							 {return 0; ok2=0;
							  break;}
							 }
					   if((tr[i]==-3)&&(ok1==1))        //Verific daca este tip C
						 {if((sir[i]==2)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 2
							 {tr[i]=2;                   //Inlocuiesc cu tip 2
							  ok1=0;}
							  if((sir[i]==3)&&(ok1==1))     //Verific daca sirul incepe cu perla normala de tip 3
							     {ok=1;                       //Pun 2 perle magice
								  tr[i]=3;
								  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
								     tr[j+2]=tr[j];          //restul transformarii : BC
								  tr[++i]=-2;                //Se completeaza cu restul transformarii
								  tr[++i]=-3;
								  k+=2; i-=2;}
							   if((sir[i]==1)&&(ok1==1))
							     {ok=1;                      //Pun perla magica
							      tr[i]=1;
								  for(j=k;j>i;j--)           //mut tot sirul cu 2 unitati in spate pt a putea pune
								     tr[j+2]=tr[j];          //restul transformarii : 2A
								  tr[++i]=2;                //Se completeaza cu restul transformarii
								  tr[++i]=-1;
								  k+=2; i-=2;}
						 }
					  }
			   }
	   }
	 }
  }
if(ok2==1)
  {ok=1;
   if(k>li)
	 return 0;
   else
     {for(i=1;((i<=k)&&(ok==1));i++)
        if(tr[i]!=sir[i])
	      ok=0;
	  return ok;}
  }
}

int main()
{int q,i,r;
ifstream g("perle.in");
ofstream t("perle.out");
g>>n;
for(q=1;q<=n;q++)
   {g>>li;
    for(i=1;i<=li;i++)
		g>>sir[i];
	r=solution();
	t<<r<<"\n";}
g.close();
t.close();
return 0;
}