#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e4 + 5;
int v[NMAX],n,poz;

bool solveC();
bool solveA() {
    if (poz >= n)
        return 0;
    poz++;
    return 1;
}
bool solveB() {
    if (poz >= n)
        return 0;
    if (v[poz] == 3) {
        poz++;
        return 0;
    }
    if (v[poz] == 2) {
        poz++;
        return solveB();
    }
    if (v[poz + 2] == 3) {
        poz++;
        if (!solveA())
            return 0;
        poz++;
        return solveA() && solveC();
    }
    return 0;
}
bool solveC() {
    if (poz >= n)
        return 0;
    if (v[poz] == 2 && poz != n - 1)
        return 0;
    if (v[poz] == 2) {
        poz++;
        return 1;
    }
    if (v[poz] == 1 && (v[poz + 1] != 2 || poz + 2 != n - 1))
        return 0;
    if (v[poz] == 1) {
        poz += 3;
        return 1;
    }
    if (poz + 4 >= n || v[poz + 2] != 3)
        return 0;
    poz++;
    return solveB() && solveC();
}
int main() 
{
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    int t;
    fin >> t;
    while (t--) {
        fin >> n;
        for (int i = 0;i < n;i++)
            fin >> v[i];
        poz = 0;
        if (solveA() && poz >= n) {
            fout << "1\n";
            continue;
        }
        poz = 0;
        if (solveB() && poz >= n) {
            fout << "1\n";
            continue;
        }
        poz = 0;
         if (solveC() && poz >= n) {
            fout << "1\n";
            continue;
        }
        fout << "0\n";
    }
    return 0;
}