#include<stdio.h>

#define NMAX 10007

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

bool C();
bool B();

bool B(){
    if(Poz <= n){
        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(Poz <= n){
        if(a[Poz] == 2){
            ++ Poz;
            return true;
        }
        if(a[Poz] == 3){
            ++ Poz;
            B();
            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");
    }

}