#include <fstream>
using namespace std;

//A -> 1 | 2 | 3
//B -> 2B | 1A3AC
//C -> 2 | 3BC | 12A

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

const int N = 10010;

short v[N], n, crt, t;

bool A();
bool B();
bool C();

bool B() {
    if (v[crt] == 2 && crt + 1 < n) {
        crt++;
        return B();
    }
    if (v[crt] == 1 && v[crt + 2] == 3 && crt + 4 < n) {
        crt += 4;
        return C();
    }
    return 0;
}

bool C() {
    if (v[crt] == 2 && crt < n) {
        crt++;
        return 1;
    }
    if (v[crt] == 3) {
        crt++;
        if (B() && crt < n)
            return C();
    }
    if (v[crt] == 1 && v[crt+1] == 2 && crt + 2 < n) {
        crt += 2;
        return 1;
    }
    return 0;
}

bool solve() {
    if (n == 1)
        return 1;
    if (v[crt] == 2 || (v[crt] == 1 && v[crt+2] == 3))
        return B();
    if (v[crt] == 3 || (v[crt] == 1 && v[crt+1] == 2))
        return C();
    return 0;
}

int main() {
    fin >> t;
    while (t--) {
        fin >> n;
        crt = 0;
        for (short i = 0; i < n; ++i)
            fin >> v[i];
        fout << solve() << "\n";
    }
}