#include<fstream>
using namespace std;
ifstream in ("perle.in");
ofstream out ("perle.out");
int x,v[10001],t,n,ok,aux;
int verifica (int ind) {
    if (ind == 1) {
        x++;
        return 1;
    }
    if (ind == 2) {
        int aux = x;
        if (v[x++] == 2 && verifica(2)) {
            return 1;
        }
        x = aux;
        if (v[x++] == 1 && verifica(1) && v[x++] == 3 && verifica(1) && verifica (3)) {
            return 1;
        }
        return 0;
    }
    if (ind == 3) {
        int aux = x;
        if (v[x++] == 2) {
            return 1;
        }
        x = aux;
        if (v[x++] == 3 && verifica(2) && verifica(3)) {
            return 1;
        }
        x = aux;
        if (v[x++] == 1 && v[x++] == 2 && verifica(1)) {
            return 1;
        }
        return 0;
    }
}

int main (void) {
    in >> t;
    for (int usl = 1; usl <= t; usl ++) {
        in >> n;
        ok = 0;
        for (int i = 1; i <= n; i ++) {
            in >> v[i];
        }
        for (int i = 1; i <= 3; i ++) {
            x = 1;
            aux = verifica (i);
            if (aux && x == n+1) {
                ok = 1;
            }
        }
        out << ok <<"\n";
    }
    return 0;
}