#include <fstream>

using namespace std;

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

int q, v[20003], n, j;
bool sol;
void b();
void c();

void b() {
    if (j > n)
        return;
    if (v[j] == 2) {
        j++;
        b();
    }
    else if (v[j] == 1 && v[j + 2] == 3) {
        j += 4;
        c();
    }
    else
        sol = false;
}

void c() {
    if (v[j] == 2)
        return;
    if (v[j] == 1 && v[j + 1] == 2 && j < n) {
        j += 2;
        return;
    }
    else if (v[j] == 3) {
        j++;
        b();
        j++;
        c();
    }
    else
        sol = false;
}
int main() {
    fin >> q;
    for (int k = 1; k <= q; k++) {
        fin >> n;
        for (int i = 1; i <= n; i++)
            fin >> v[i];
        if (n == 1) {
            fout << 1 << '\n';
            continue;
        }
        sol = true;
        if (v[0] > 3 != v[0]) {
            fout << 0 << '\n';
            continue;
        }
        j = 1;
        if (v[j] == 1)
            if (n == 3)
                c();
            else
                b();
        else if (v[j] == 2)
            b();
        else
            c();
        if (j != n)
            sol = false;
        fout << sol << '\n';
    }
    return 0;
}