#include <stdio.h>
#include <string.h>

#define FISIN     "perle.in"
#define FISOUT    "perle.out"
FILE *fin, *fout;

#define MAXN 10010
char buffer[MAXN];

int try_a(int st, int en);
int try_b(int st, int en);
int try_c(int st, int en);

int try_a(int st, int en) {
  if (st >= en) return -1;
  return st + 1;
}

int try_b(int st, int en) {
  for (;;) {
    if (st >= en) return -1;    
    if (buffer[st] == '3') return -1;
    if (buffer[st] == '2') { ++st; continue; }
    break;
  } 

  if (st >= en || buffer[st] != '1') return -1; ++st; // 1
  if (st >= en) return -1; ++st; // A
  if (st >= en || buffer[st] != '3') return -1; ++st; // 3
  if (st >= en) return -1; ++st; // A
  return try_c(st, en);
}

int try_c(int st, int en) {
  if (st >= en) return -1;
  switch (buffer[st]) {
  case '1' :
    if (st >= en || buffer[st] != '1') return -1; ++st; // 1
    if (st >= en || buffer[st] != '2') return -1; ++st; // 1
    if (st >= en) return -1; ++st; // A
    return st;
    
  case '2' : 
    return st + 1;

  case '3' :
    if (st >= en || buffer[st] != '3') return -1; ++st; // 1
    int tmp = try_b(st, en); if (tmp == -1) return -1;
    return try_c(tmp, en);
  }

  return -1;
}

int main() {
  fin = fopen(FISIN, "rt");
  fout = fopen(FISOUT, "wt");
  
  int nrt;
  fscanf(fin, "%d", &nrt);
  for (int ttt = 0; ttt < nrt; ++ttt) {
    int n; fscanf(fin, "%d", &n);
    memset(buffer, 0, sizeof(buffer));
    for (int i = 0; i < n; ++i) {
      int a; fscanf(fin, "%d", &a);
      buffer[i] = '0' + a;
    }

    bool ok = (try_a(0, n) == n) || (try_b(0, n) == n) || (try_c(0, n) == n);
    fprintf(fout, "%d\n", ok ? 1 : 0);
  }

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