#include <cstdio>

int cursor, err;

const int MAX_L = 10000;
const int END = 0;

int v[MAX_L + 1];

void queryDigit(int x) {
  if(!err) {
    if(v[cursor] != x)
      err = 1;
    cursor++;
  }
}

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

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

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

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

int main() {
  int t, i, n, j;
  FILE *fin = fopen("perle.in", "r");
  FILE *fout = fopen("perle.out", "w");

  fscanf(fin, "%d", &t);
  for(i = 0; i < t; i++) {
    fscanf(fin, "%d", &n);
    for(j = 0; j < n; j++)
      fscanf(fin, "%d", &v[j]);
    v[n] = END;
    cursor = err = 0;
    A();
    if(cursor != n || err) {
      cursor = err = 0;
      B();
      if(cursor != n || err) {
        cursor = err = 0;
        C();
        if(cursor != n || err)
          fprintf(fout, "0\n");
        else
          fprintf(fout, "1\n");
      } else
        fprintf(fout, "1\n");
    } else
      fprintf(fout, "1\n");
  }

  fclose(fin);
  fclose(fout);
  return 0;
}