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

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

int v[10005], p, ok;

void b();
void c();

void b() {
    if (v[p] == 2) {
        p++;
        b();
    }
    else if (v[p] == 1 && v[p+2] == 3) {
        p = p + 4;
        c();
    }
    else {
        ok = 0;
        return;
    }
}

void c() {
    if (v[p] == 2)
        p++;
    else if (v[p] == 3) {
        p++;
        b();
        c();
    }
    else if (v[p] == 1 && v[p+1] == 2) {
        p = p + 3;
    }
    else {
        ok = 0;
        return;
    }
}

int main()
{
    int afis, nr, n;
    fin >> nr;
    for (int i=0; i<nr; i++) {
        afis = 0;
        memset(v, 0, sizeof(v));
        fin >> n;
        if (n == 1) {
            fin >> v[0];
            fout << "1\n";
        }
        else {
            for (int j=0; j<n; j++)
                fin >> v[j];
            p = 0;
            ok = 1;
            b();
            if (ok == 1 && p == n) {
                afis = 1;
                fout << "1\n";
            }
            p = 0;
            ok = 1;
            c();
            if (ok == 1 && p == n) {
                afis = 1;
                fout << "1\n";
            }
            if (afis == 0) {
                fout << "0\n";
            }
        }
    }
    return 0;
}