#include <fstream>
#define DEF 10010

using namespace std;

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

int nrTests, iPos, szN, vPerls[DEF];

int A ();

int B ();

int C ();

int A () {
    if (iPos > szN) {
        return false;
    }

    if (vPerls[iPos] == 1 or vPerls[iPos] == 2 or vPerls[iPos] == 3) {
        ++ iPos;
        return true;
    }

    return false;
}

int B () {
    if (iPos > szN) {
        return false;
    }

    if (vPerls[iPos] == 2) {
        ++ iPos;
        return B ();
    }

    if (vPerls[iPos ++] == 1 and A() and vPerls[iPos ++] == 3 and A () and C ()) {
        return true;
    }

    return false;

}

int C () {
    if (iPos > szN) {
        return false;
    }

    if (vPerls[iPos] == 2) {
        ++ iPos;
        return true;
    }

    if (vPerls[iPos] == 3) {
        ++ iPos;
        if (B () and C ()) {
            return true;
        }
        return false;
    }

    if (vPerls[iPos ++] == 1 and vPerls[iPos ++] == 2 and A ()) {
        return true;
    }

    return false;
}

int main () {

    fin >> nrTests;

    for (; nrTests; -- nrTests) {

        fin >> szN;
        for (int i = 1; i <= szN; ++ i) {
            fin >> vPerls[i];
        }

        int res;
        iPos = 1;
        res = A ();
        if (res == true and iPos == szN + 1) {
            fout << "1\n";
            continue;
        }

        iPos = 1;
        res = B ();
        if (res == true and iPos == szN + 1) {
            fout << "1\n";
            continue;
        }

        iPos = 1;
        res = C ();
        if (res == true and iPos == szN + 1) {
            fout << "1\n";
            continue;
        }

        fout << "0\n";

    }

    return 0;
}