#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);  
}*/