#include <fstream>
#include <vector>

using namespace std;

inline bool IsA(const vector<int> &vec, int left, int right)
{
  return left == right;
}

bool IsC(const vector<int> &vec, int left, int right);

bool IsB(const vector<int> &vec, int left, int right)
{
  if (vec[left] == 3) {
    return false;
  } else if (vec[left] == 1) {
    return left + 4 <= right && vec[left + 2] == 3 && IsC(vec, left + 4, right);
  } else {
    return left + 1 <= right && IsB(vec, left + 1, right);
  }
}

bool IsC(const vector<int> &vec, int left, int right)
{
  if (vec[left] == 2) {
    return left == right;
  } else if (vec[left] == 1) {
    return left + 2 == right && vec[left + 1] == 2;
  } else {
    for (int i = left + 1; i < right; ++i) {
      if (IsB(vec, left + 1, i) && IsC(vec, i + 1, right)) {
        return true;
      }
    }
  }
  return false;
}

inline bool Good(const vector<int> &vec)
{
  auto end = vec.size() - 1;
  return IsA(vec, 0, end) || IsB(vec, 0, end) || IsC(vec, 0, end);
}

int main()
{
  ifstream fin("perle.in");
  ofstream fout("perle.out");

  int tests;
  fin >> tests;

  for (int i = 0; i < tests; ++i) {
    int size;
    fin >> size;

    vector<int> vec(size);
    for (auto &elem : vec) {
      fin >> elem;
    }
    fout << (Good(vec) ? 1 : 0) << "\n";
  }
  return 0;
}