#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX (1<<15)
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
int n,t,x,pozitie,v[NMAX];
void C();
void A()
{
    if(pozitie) pozitie++;
}
void B()
{
  if(!pozitie) return;
  if(v[pozitie]==2)
  {
      pozitie++;
      B();
  }
  else if(v[pozitie]==1)
  {
      pozitie++;
      A();
      if(v[pozitie]!=3)
      {
          pozitie=0;
          return;
      }
      pozitie++;
      A();
      C();
  }
  else pozitie=0;
}
void C()
{
    if(!pozitie) return;
    if(v[pozitie]==2) pozitie++;
   else if(v[pozitie]==1)
   {
       pozitie++;
       if(v[pozitie]!=2)
       {
           pozitie=0;
           return;
       }
       pozitie++;
       A();
   }
   else
   {
       pozitie++;
       B();
       C();
   }
}


void rezolva(int t)
{ for(int k=1;k<=t;k++)
    in>>v[k];
   bool ok=false;
   pozitie=1;
   A();
   if(pozitie==t+1) ok=true;
   pozitie=1;
   B();
   if(pozitie==t+1) ok=true;
   pozitie=1;
   C();
   if(pozitie==t+1) ok=true;
   out<<ok<<'\n';
}
int main()
{  in>>n;
for(int i=1;i<=n;i++)
  {
      in>>t;
      rezolva(t);
  }
    return 0;
}