#include <stdio.h>
#include <string.h>

#define FIN "perle.in"
#define FOUT "perle.out"
#define nmax 100001

int v[nmax], s[nmax], poz,N,SOL;

void putB();
void putC();

void putA()
 {
  s[poz]=v[poz];
  ++poz;
 }

void putB()
 {
  if(v[poz]==2)
   {
    s[poz]=2;
    ++poz;
    putB();
   }
    else
   if(v[poz]==1)
   {
    s[poz]=1;
    ++poz;
    putA();
    if(v[poz]==3)
     {
      s[poz]=3;
      ++poz;
      putA();
      putC();
     }
      else
     SOL=-1;
   }
    else
   SOL=-1;
 }

void putC()
 {
  if(v[poz]==2)
   {
    s[poz]=2;
    ++poz;
   }
    else
  if(v[poz]==3)
   {
    s[poz]=3;
    ++poz;
    putB();
    putC();
   }
    else
   {
    s[poz]=1;
    ++poz;
    if(v[poz]!=2)
     SOL=-1;
      else
     {
      s[poz]=2;
      ++poz;
      putA();
     }
   }
    
 }

void rez()
 {
  if(v[poz]==1)
   {
    if(s[0]==1)
    putA();
     else
    if(s[0]==3)
    putC();
     else
    if(s[0]>=5)
    putB();
     else
    SOL=-1;
   }
    else
  if(v[poz]==2)
   {
    if(s[0]==1)
    putA();
     else
    putB();
   }
    else
   if(s[0]==1)
    putA();
     else
    putC();
 }

int main()
 {
  freopen(FIN,"r",stdin);
  freopen(FOUT,"w",stdout);

  int i,j,T;

  scanf("%d", &T);

  for(i=1;i<=T;++i)
   {
    scanf("%d", &N);

    memset(&v,0,sizeof(v));

    for(j=1;j<=N;++j)
     scanf("%d", &v[j]);
     
    memset(&s,0,sizeof(s));
    s[0]=N;  poz=1;
    SOL=0;
    rez();
    if(s[poz]!=0 && poz>N)
     SOL=-1;
    if(!SOL)
     printf("1\n");
      else
     printf("0\n");
   }

  return 0;
 }