#include <cstdio>

const int MAXN = 1e5;

int v[MAXN + 4];

inline int C(int cursor);

inline int B(int cursor) {
  if (v[cursor] == 2) {
    return B(cursor + 1);
  } else if (v[cursor] == 1 && v[cursor + 2] == 3) {
    return C(cursor + 4);
  } else {
    return -1;
  }
}

inline int C(int cursor) {
  if (v[cursor] == 2) {
    return cursor + 1;
  } else if (v[cursor] == 3) {
    return C(B(cursor + 1));
  } else if (v[cursor] == 1 && v[cursor + 1] == 2) {
    return cursor + 3;
  } else {
    return -1;
  }
}

int main() {
  int t, n;
  FILE *fin = fopen("perle.in", "r");
  fscanf(fin, "%d", &t);
  FILE *fout = fopen("perle.out", "w");
  for (; t > 0; --t) {
    fscanf(fin, "%d", &n);
    for (int i = 1; i <= n; ++i) {
      fscanf(fin, "%d", &v[i]);
    }
    if (B(1) == n + 1 || C(1) == n + 1 || n == 1) {
      fprintf(fout, "1\n");
    } else {
      fprintf(fout, "0\n");
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}