#include <cstdio>

using namespace std;

const int N = 10005;
int n, t, v[N];

int verifica(int ind, int tip, int &poz)
{
    if(ind > n)
        return 0;
        
    if(tip == 1) {
        poz = ind;
        return 1;
    }

    if(tip == 2) {
        if(v[ind] == 2) {
            if(verifica(ind + 1, 2, poz))
                return 1;
            else return 0;
        }
        else if(v[ind] == 1) {
            if(ind + 4 <= n && v[ind + 2] == 3 && verifica(ind + 4, 3, poz))
                    return 1;
            else return 0;

        }
        return 0;
    }

    if(tip == 3) {
        if(v[ind] == 2) {
            poz = ind;
            return 1;
        }
        if(v[ind] == 3) {
            if(verifica(ind + 1, 2, poz) && verifica(poz + 1, 3, poz))
                return 1;
            else return 0;
        }
        if(v[ind] == 1) {
            if(ind + 2 <= n && v[ind + 1] == 2 && verifica(ind + 2, 1, poz))
                return 1;
            else return 0;
        }

    }
    return 0;
}

int main()
{
    freopen ("perle.in", "r", stdin);
    freopen ("perle.out", "w", stdout);

    scanf("%d", &t);
    for(int i = 1; i <= t; ++i) {
        scanf("%d", &n);
        for(int j = 1; j <= n; ++j)
            scanf("%d", &v[j]);

        int poz;
        if(verifica(1, 1, poz) && poz == n)
            printf("1\n");
        else if(verifica(1, 2, poz) && poz == n)
            printf("1\n");
        else if(verifica(1, 3, poz) && poz == n)
            printf("1\n");
        else printf("0\n");
    }
}