#include <iostream>
#include <fstream>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
//A -> 1 ; 2 ; 3
//B -> 2B ; 1A3AC
//C -> 2 ; 3BC ; 12A


void caz_C();
void caz_B();
int N, v[10001], l, ok, j;
int main() {
    in >> N;
    for (int i = 1; i <= N; ++i) {
        in >> l;
        for (j = 1; j <= l; ++j)
            in >> v[j];
        ok = 1;
        if (l == 1) {
            out << ok << endl;
            continue;
        }
        j = 1;
        if (v[1] == 1) {
            if (l == 3)
                caz_C();
            else
                caz_B();
        }else if (v[1] == 2)
                caz_B();
        else
                caz_C();
        if (j != l)
            ok = 0;
        out << ok << endl;
    }
    return 0;
}

void caz_B() {
    if (j > l)
        return;
    if (v[j] == 2) {
        ++j;
        caz_B();
    }else if (v[j] == 1 && v[j+2] == 3) {
        j += 4;
        caz_C();
    }else
        ok = 0;
}

void caz_C() {
    if (v[j] == 2)
        return;
    if (v[j] == 1 && v[j+1] == 2) {
        j += 2;
        return;
    }
    if (v[j] == 3)  {
        ++j;
        caz_B();
        ++j;
        caz_C();
    }else
        ok = 0;
}