#include<stdio.h>

#define NMAX 10007

int n, Poz, T;
int a[NMAX];

bool C();

bool B(){
    if(n - Poz >= 3)
        if(a[Poz] == 1 && a[Poz + 2] == 3){
            Poz += 4;
            return C();
        }
    if(a[Poz] == 2){
        ++ Poz;
        return B();
    }
    return false;
}

bool C(){
    if(a[Poz] == 2){
        ++ Poz;
        return true;
    }
    if(a[Poz] == 3){
        ++ Poz;
        B();
        ++ Poz;
        return C();
    }
    if(a[Poz] == 1 && a[Poz + 1] == 2){
        Poz += 3;
        return true;
    }
    return false;
}

int main(){
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    for(scanf("%d", &T); T > 0; -- T){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i)
            scanf("%d", &a[i]);
        Poz = 1;
        int Rez1 = 0, Rez2 = 0;
        int ok = B();
        if(ok == 1 && Poz > n)
            Rez1 = 1;
        Poz = 1;
        ok = C();
        if(ok == 1 && Poz > n)
            Rez2 = 1;
        if(Rez1 == 1 || Rez2 == 1 || n == 1)
            printf("1\n");
        else
            printf("0\n");
    }

}