#include<fstream.h>
ifstream f("perle.in");
ofstream g("perle.out");
const unsigned nmax=10005;
struct nod{int val; unsigned urm;} lista[nmax+1];
int x,n,a[nmax],nrel=1;

int liber(){int i=0;
while(lista[i].val!=0)i++;
return i;}

void inceput(){
int i=0;
while(nrel!=1&&i<nmax)
   {lista[i].val=0;
   i=lista[i].urm;
   nrel--;
  }
}


int ad(int c,int d,int e)
{int q,p,pp;
q=lista[c].urm;
if(d==4){lista[c].val=e;return 1;}
if(d==5)
{   if(e==2)
    {  lista[c].val=2;
       p=liber();
       lista[c].urm=p;
       lista[p].val=5;
       lista[p].urm=q;
       nrel++;
       return 1;
    }
    if(e==1)
    {  lista[c].val=1;
       p=liber();
       lista[c].urm=p;
       lista[p].val=4;
       pp=liber();
       lista[p].urm=pp;
       lista[pp].val=3;
       p=liber();
       lista[pp].urm=p;
       lista[p].val=4;
       pp=liber();
       lista[p].urm=pp;
       lista[pp].val=6;      
       lista[pp].urm=q;
       nrel+=4; 
       return 1;
    }
    return 0;
}
if(d==6)
{   if(e==2)
    {  lista[c].val=2;
       lista[c].urm=q;
       return 1;
    }
    if(e==1)
    {  lista[c].val=1;
       p=liber();
       lista[c].urm=p;
       lista[p].val=2;
       pp=liber();
       lista[p].urm=pp;
       lista[pp].val=4;
       lista[pp].urm=q;
       nrel+=2;
       return 1;
    }
    if(e==3)
    {  lista[c].val=3;
       p=liber();
       lista[c].urm=p;
       lista[p].val=5;
       pp=liber();
       lista[p].urm=pp;
       lista[pp].val=6;
       lista[pp].urm=q;
       nrel+=2;
       return 1;
    }
    return 0;
}}


int main(){
int i,j,ii,k,p,e;
inceput();
f>>n;
for(i=0;i<n;i++)
{    f>>x;
     for(j=0;j<x;j++) f>>a[j];
     e=1;
     if(x==1) e=2;
     else
	for(ii=0;ii<2;ii++)
	{   e=1;
            inceput(); lista[0].urm=10; lista[10].val=-1;
	    if(ad(0,ii+5,a[0]))
	       for(j=0,k=0;j<x;j++)
	       {
		    




	            if(lista[k].val>3)
	         	  if(!ad(k,lista[k].val,a[j]))
	                 {    
			      e=0;
			   
                              j=x;
		              break;
			 }


		   if(lista[k].val!=a[j])
		   {      
		       e=0;       
                       j=x;
		       break;
		   }
		   if(j+1==nrel)k=liber();
		   else k=lista[k].urm;
	       } 
                    
            else e=0;  
	    if(e&&nrel==x)
	      {  e=2;    

	         ii=2;
	         break;
	      }

	}
     if(e==2)
	g<<1<<"\n";
     else
	g<<0<<"\n";
}


f.close();
g.close();

return 0;}