#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 (right - left < 4) {
    return false;
  }

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

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

    if (right - left < 5) {
      return false;
    } else if (vec[right - 1] == 2 && vec[right - 2] == 1 && IsB(vec, left + 1, right - 3)) {
      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;
}