#include<cstdio>

const int NMAX=10001;

int v[NMAX+1];
int poz,n;

bool A();
bool B();
bool C();

bool A()
{
 if(poz!=1)
    {
     poz++;
     return true;
    }
 return false;
}

bool B()
{
 if(v[poz]==2)
    {
     poz++;
     if(!B())
        {
         poz--;
         return false;
        }
     return true;
    }
 if(v[poz]==1)
    {
     poz++;
     if(!A())
        {
         poz--;
         return false;
        }
     if(v[poz]==3)
        {
         poz++;
         if(!A())
            {
             poz-=2;
             return false;
            }
         if(!C())
            {
             poz--;
             return false;
            }
         return true;
        }
     else
        {
         poz--;
         return false;
        }
    }
 return false;
}

bool C()
{
 if(v[poz]==2)
    {
     poz++;
     return true;
    }
 if(v[poz]==3)
    {
     poz++;
     if(!B())
        {
         poz--;
         return false;
        }
     if(!C())
        {
         poz--;
         return false;
        }
     return true;
    }
 if(v[poz]==1)
    {
     poz++;
     if(v[poz]==2)
        {
         poz++;
         if(!A())
            {
             poz-=2;
             return false;
            }
         return true;
        }
     else
        poz--;
     return false;
    }
 return false;
}

int main()
{
 FILE *in=fopen("perle.in","r");
 int nr_teste;
 fscanf(in,"%d ",&nr_teste);
 FILE *out=fopen("perle.out","w");
 for(int q=1;q<=nr_teste;q++)
     {
      fscanf(in,"%d ",&n);
      for(int i=1;i<=n;i++)
          {
           fscanf(in,"%d ",&v[i]);
          }
      if(n==1)
         {
          fprintf(out,"1\n");
          continue;
         }
      poz=1;
      if(A() && poz==n+1)
         {
          fprintf(out,"1\n");
          continue;
         }
      poz=1;
      if(B() && poz==n+1)
         {
          fprintf(out,"1\n");
          continue;
         }
      poz=1;
      if(C() && poz==n+1)
         {
          fprintf(out,"1\n");
          continue;
         }
      fprintf(out,"0\n");
     }
 fclose(in);
 fclose(out);
 return 0;
}