#include <cstdio>
using namespace std;

bool ok;
int v[10005];
int l;
int A(int k);
int B(int k);
int C(int k);

int A(int k) {
    return k+1;
}

int B(int k) {
    if (ok || k > l) return 0;
    if (v[k] == 2) return B(k+1);
    else if (v[k] == 1 && v[k+2] == 3) return C(k+4);
    else return 0;
}
int C(int k) {
    if (ok || k > l) return 0;
    if (v[k] == 2) return k;
    else if (v[k] == 3) {
        int nr = B(k+1);
        return C(nr+1);
    } else if (v[k] == 1 && v[k+1] == 2) {
        return k+2;
    }
    else return 0;
}

int main() {
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int t;
    scanf("%d",&t);
    while (t--) {
        ok = false;
        scanf("%d",&l);
        for (int i=1;i<=l;i++) {
            scanf("%d",&v[i]);
        }
        if (l == 1) ok = true;
        else if (v[1] == 1) {
            if (B(1) == l) ok = true;
            if (C(1) == l) ok = true;
        } else if (v[1] == 2) {
            if (B(1) == l) ok = true;
            if (C(1) == l) ok = true;
        } else if (v[1] == 3) {
            if (C(1) == l) ok = true;
        }
        if (ok) printf("1\n");
        else printf("0\n");
    }
    return 0;
}