#include<fstream.h>

#define xx 10001

ifstream fin("perle.in");
ofstream fout("perle.out");

int n,nr,a[xx];

int b(int);
int c(int);

int rezolvare()
{
    int sw=-1;
    
    if(n==1)
       sw=1;
    else
       if(n==2)
          sw=0;
       else
          if(a[1]==3)
              sw=c(1);  
          else
              if(a[1]==1 && a[3]==3 && n>=4)
                 sw=b(1);
              else
                  if(a[1]==1 && a[2]==2 && n>=3)
                      sw=c(1);
                  else
                     if(a[1]==2)
                        sw=b(1);
    return (sw!=-1 ? sw : 0);
}

int main()
{
    int i,j;
    fin>>nr;
    
    for(i=1;i<=nr;i++)
    {
       fin>>n;
       memset(a,0,sizeof(a));
       
       for(j=1;j<=n;j++)
         fin>>a[j];
       
       fout<<rezolvare()<<'\n';
    }
    
    fout.close();
    return 0;
}

/*
int b(int i)
{
    int sw=-1;
    
    if(a[i]==2)
        sw=b(i+1);
    else
       if(a[i]==1 && a[i+2]==3)
          sw=c(i+4);
    return (sw!=-1 ? sw : 0);
}
*/

int b(int i)
{
	if(a[i]==2)
		return b(i+1);
	if(a[i]==1 && a[i+2]==3)
		return c(i+4);
	return c(i+1);
}

int c(int i)
{
	if(a[i]==2)
	{
		if(i==n)
			return 1;
		return c(i+1);  // c->2
	}
	if(a[i]==1 && a[i+1]==2)
	{
		if(i+2==n)
			return 1;
		return c(i+3); // c->12a
	}
	if(a[i]==3)
		return b(i+1); // c->3bc
	return 0;
}

/*int c(int i)
{
    int sw=-1;
    
    if(a[i]==2)
    {
       if(i==n)
         return 1;
    }
    else
       if(a[i]==1 && a[i+1]==2)
       {
          if(i+2==n)
             return 1;
       }
       else
         if(a[i]==3)
            sw=b(i+1);
    return (sw!=-1 ? sw : 0);
}*/