#include <fstream>

using namespace std;
int v[10010];
int i,n,q;

int a(),b(),c();

int a() {               ///returneaza 1 daca se poate forma o secventa care incepe pe pozitia i cu perla a
    if (i>n) return 0;
    if (v[i]==1||v[i]==2||v[i]==3) {
        i++;
        return 1;
    }
    else return 0;
}

int b() {
    if (i>n) return 0;
    if (v[i]==2) {
        i++;
        return b();
    }
    else if (v[i]==1) {
        i++;
        if (a()==0) return 0;
        if (v[i]!=3) return 0;
        i++;
        if (a()==0) return 0;
        return c();
    }
    else return 0;
}

int c() {
    if (i>n) return 0;
    if (v[i]==2) {
        i++;
        return 1;
    }
    else if (v[i]==3) {
        i++;
        if (b()==0) return 0;
        return c();
    }
    else if (v[i]==1&&v[i+1]==2) {
        i+=2;
        return a();
    }
    else return 0;
}

int main() {
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    fin>>q;
    while (q--) {
        fin>>n;
        for (i=1;i<=n;i++) {
            fin>>v[i];
        }
        i=1;
        if (a()&&i==n+1) {
            fout<<1<<"\n";
            continue;
        }
        i=1;
        if (b()&&i==n+1) {
            fout<<1<<"\n";
            continue;
        }
        i=1;
        if (c()&&i==n+1) {
            fout<<1<<"\n";
            continue;
        }
        else fout<<0<<"\n";
    }
    return 0;
}