#include <stdio.h>
int v[10010], p=0, lim;
/*
bool A(){
  p++;
  return true;
}*/
bool B();
bool C();

int main()
{
  FILE *fi=fopen("perle.in", "r"), *fo=fopen("perle.out", "w");
  int m, n, i, j;
  fscanf(fi, "%d", &m);
  for(j=0;j<m;j++){
    fscanf(fi, "%d", &n);
    for(i=0;i<n;i++)
      fscanf(fi, "%d", &v[i]);
    if(n==1)
      fprintf(fo, "1\n");
    else{
    p=0;
    lim=n;
    if(B() && p==lim)
      fprintf(fo, "1\n");
    else{
      p=0;
      if(C() && p==lim)
        fprintf(fo, "1\n");
      else
        fprintf(fo, "0\n");
    }
    }
  }
  fclose(fi);
  fclose(fo);
  return 0;
}

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

bool C(){
  if(v[p]==2){
    p++;
    return true;
  }
  else if(v[p]==3){
    p++;
    if(B()){
      if(C())
        return true;
      else
        return false;
    }
    else
      return false;
  }
  else if(v[p]==1 && v[p+1]==2){
    p+=3;
    return true;
  }
  return false;
}