#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;
using ld = long double;
class Grammar {
  vector<int> v;

  size_t was_A(size_t left) { return left < v.size() ? left + 1 : 0; }

  size_t was_B(size_t left) {
    if (left >= v.size())
      return 0;
    if (v[left] == 2)
      return was_B(left + 1);
    if (left + 4 >= v.size())
      return 0;
    if (v[left] == 1 && v[left + 2] == 3)
      return was_C(left + 4);
    return 0;
  }

  size_t was_C(size_t left) {
    if (left >= v.size())
      return 0;
    if (v[left] == 2)
      return left + 1;

    if (v.size() > left + 1 && v[left] == 1 && v[left + 1] == 2)
      return was_A(left + 2);

    if (v[left] != 3)
      return false;

    size_t curr = was_B(left + 1);
    if (curr == 0)
      return 0;

    return was_C(curr);
  }

public:
  bool check(vector<int> &_v) {
    v = std::move(_v);
    return was_A(0) == v.size() || was_B(0) == v.size() || was_C(0) == v.size();
  }
};

void solve() {
  int n;
  cin >> n;

  vector<int> v(n);
  for (auto &x : v)
    cin >> x;

  Grammar g;
  cout << g.check(v) << '\n';
}

int main() {
  freopen("perle.in", "r", stdin);
  freopen("perle.out", "w", stdout);
  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}