#include <iostream>
#include <fstream>

using namespace std;
ifstream in ("perle.in");
ofstream out ("perle.out");
int v[10001];
int pointer = 0, err = 0;
void A();
void B();
void C();


void A(){
  if(!err)
    pointer++;
}

void B(){
  if(!err){
    if(v[pointer] == 2){
      pointer++;
      B();
    }
    else if(v[pointer] == 1){
      pointer++;
      A();
      if(v[pointer] != 3)
        err = 1;
      pointer++;
      A();
      C();
    }
    else
      err = 1;
  }
}

void C(){
  if(!err){
    if(v[pointer] == 2){
      //cout<<"2";
      pointer++;
    }
    else if(v[pointer] == 3){
     // cout<<"3";
      pointer++;
      B();
      C();
    }
    else if(v[pointer] == 1){
   //   cout<<"1";
      pointer++;
      if(v[pointer] != 2){
        err = 1;
      }
      pointer++;
      A();
    }
  }
}

int main()
{
    int n , i ,j ,a;
    in>>n;
    for(i = 0 ; i < n ;i++){
      in>>a;
      for(j = 0 ; j < a ;j++){
        in>>v[j];
      }
      v[a] = 0;
      err = 0;
      pointer = 0;
      A();
      if(pointer != a || err){
        err = 0;
        pointer = 0;
        B();
        //cout<<pointer<<" "<<err;
        if(pointer != a || err){
          err = 0;
          pointer = 0;
          C();
          if(pointer != a || err)
            out<<0<<'\n';
          else
            out<<1<<'\n';
        }
        else out<<1<<'\n';
      }
      else out<<1<<'\n';
    }
    return 0;
}