#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];
        if (l == 1) {
            out << 1 << endl;
            continue;
        }else if (l == 2) {
            out << 0 << endl;
            continue;
        }
        ok = 1;
        j = 1;
        if (v[1] == 1) {
            if (l == 3)
                caz_C();
            else
                caz_B();
        }else if (v[1] == 2)
                caz_B();
        else
            caz_C();
        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 (j > l)
        return;
    if (v[j] == 2 && j == l) {
        ++j;
        caz_C();
    }else if (v[j] == 3)  {
        ++j;
        caz_B();
        ++j;
        caz_C();
    }else if (v[j] == 1 && v[j+1] == 2 && j + 2 == l) {
        j += 3;
        caz_C();
    }else
        ok = 0;
}