#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAX_N = 10100;

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

int T;
int sir[MAX_N];

bool attempt_rebuild();
int use_B(int), use_C(int);

int main() {
    fin >> T;
    for (int i = 1; i <= T; ++i) {
        fin >> sir[0];
        for (int j = 1; j <= sir[0]; ++j) {
            fin >> sir[j];
        }
        if (attempt_rebuild()) fout << 1 << '\n';
        else fout << 0 << '\n';
    }
    return 0;
}

bool attempt_rebuild() {
    if (sir[0] == 1) return true;
    if (use_B(1) == sir[0] + 1) return true;
    if (use_C(1) == sir[0] + 1) return true;
    return false;
}

int use_B(int position) {
    if (position > sir[0] + 1) return position;
    if (sir[position] == 2) return use_B(position + 1);
    if (sir[position] == 1 && sir[position + 2] == 3) return use_C(position + 4);
    return sir[0] + 2;
}

int use_C(int position) {
    if (position > sir[0] + 1) return position;
    if (sir[position] == 2) return position + 1;
    if (sir[position] == 3) return use_C(use_B(position + 1));
    if (sir[position] == 1 && sir[position + 1] == 2) return position + 3;
    return sir[0] + 2;
}