#include <iostream>
#include <fstream>
using namespace std;

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

const int MAXL = 10009;
int T, poz, NrCaractere;
int v[MAXL];
bool isB(), isC();

bool isB() {
    if (poz > NrCaractere - 5) return false;//nu ajung caracterele ramase, deci nu pot forma B
    if (v[poz] == 2) {
        ++poz;
        return isB();
    }else
    if (v[poz] == 1 && v[poz + 2] == 3) {
        poz += 4;
        if (v[poz] == 2) {
            ++poz;
            return true;
        }
        else if (isC())
            return true;
        return false;
    }
    return false;
}

bool isC() {
    if (v[poz] == 2) {
        ++poz;
        return true;
    }
    if (v[poz] == 3) {
        ++poz;
        return isB() && isC();
    }
    if (poz <= NrCaractere - 3 && v[poz] == 1 && v[poz + 1] == 2) {
        poz += 3;
        return true;
    }
    return false;
}

void Read() {
    fin >> NrCaractere;
    for (int i = 0; i < NrCaractere; ++i)
        fin >> v[i];
}

int main() {
    fin >> T;
    while (T--) {
        Read();
        poz = 0;
        if (NrCaractere == 1)//se poate forma din A
            fout << 1;
        else//nu se poate forma din A, deci trebuie sa vedem daca se poate forma din B sau C
        if (isB() && poz == NrCaractere)
            fout << 1;
        else {
            poz = 0;
            if (isC() && poz == NrCaractere)
                fout << 1;
            else fout << 0;
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}