#include <iostream>
#include <fstream>

using namespace std;

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


int N, L, v[12000];
bool ok = false, stop = false;

void Solve()
{
    if (L != 1 && !stop){
        int aux = 4;
        if (v[L-3] == 1 && v[L-2] == 2){
            v[L-3] = 9;
            L -= 2;
            --aux;
        }
        if (v[L-5] == 1 && v[L-2] == 2 && v[L-1] == 9){
            v[L-5] = 8;
            L -= 4;
            --aux;
        }
        if (v[L-3] == 3 && v[L-2] == 8 && v[L-1] == 9){
            v[L-3] = 9;
            L -= 2;
            --aux;
        }
        if (v[L-2] == 2 && v[L-1] == 8){
            v[L-2] = 8;
            L -= 1;
            --aux;
        }
        if (aux == 4)
            stop = true;
        Solve();
    }
    else if (L == 1 && !stop){
        ok = true;
    }
}

void Read()
{
    fin >> N;
    for (int i = 0; i < N; ++i){
        fin >> L;
        for (int j = 0; j < L; ++j)
            fin >> v[j];
        Solve();
        if (ok){
            fout << 1 << "\n";
            ok = false;
        }
        else{
            fout << 0 << "\n";
            stop = false;
        }
    }
}

int main()
{
    Read();
    return 0;
}