#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;

bool was_C(const vector<int> &, int, int);

bool was_A(const vector<int> &v, int left, int right) { return right == left + 1; }

bool was_B(const vector<int> &v, int left, int right) {
  if (left >= right)
    return false;
  if (v[left] == 2 && was_B(v, left + 1, right))
    return true;
  if (left + 4 >= right)
    return false;
  if (v[left] == 1 && v[left + 2] == 3 && was_C(v, left + 4, right))
    return true;
  return false;
}

bool was_C(const vector<int> &v, int left, int right) {
  if (right == left + 1 && v[left] == 2)
    return true;

  if (right == left + 3 && v[left] == 1 && v[left + 1] == 2)
    return true;

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

  for (size_t len_B = 5; len_B < right - left - 1; ++len_B)
    if (was_B(v, left + 1, left + 1 + len_B) && was_C(v, left + 1 + len_B, right))
      return true;

  return false;
}

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

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

  cout << (was_A(v, 0, n) || was_B(v, 0, n) || was_C(v, 0, n)) << '\n';
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
#endif
  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}