#include<cstring>
#include<fstream>

using namespace std;

int siz, p, a[100005];

void A();
void B();
void C();

void A(){
  ++p;
}

void B(){
  if(a[p] == 2){
    ++p;
    B();
    return;
  }
  else if(a[p] == 1 && a[p + 2] == 3){
    p += 4;
    C();
    return;
  }
  p = -1;
}

void C(){
  if(a[p] == 2){
    ++p;
    return;
  }
  else if(a[p] == 3){
    ++p;
    B();
    if(p == -1)
      return;
    C();
  }
  else if(a[p] == 1 && a[p + 1] == 2){
    p += 3;
    return;
  }
  p = -1;
}

int main(){
  ifstream in("perle.in");
  ofstream out("perle.out");

  int tests;
  in >> tests;

  for(int i = 1; i <= tests; ++i){
    in >> siz;
    for(int i = 1; i <= siz; ++i)
      in >> a[i];
    a[siz + 1] = a[siz + 2] = a[siz + 3] = a[siz + 4] = -1;
    p = 2;
    if(p == siz + 1)
      out << "1\n";
    else{
      p = 1;
      B();
      if(p == siz + 1)
        out << "1\n";
      else{
        p = 1;
        C();
        if(p == siz + 1)
          out << "1\n";
        else
          out << "0\n";
      }
    }
  }

  return 0;
}