#include<stdio.h>
int N,T,nr[10100];
int B(int x);
int C(int x){
    if(x>N || x<0)
        return -1;
    if(nr[x]==2)
        return x+1;
    if(nr[x]==1){
        if(nr[x+1]==2)
            return x+3;
        else
            return -1;
    }
    return C(B(x+1));
}
int B(int x){
    if(x>N || x<0)
        return -1;
    if(nr[x]==2)
        return B(x+1);
    if(nr[x]==1 && nr[x+2]==3)
        return C(x+4);
    return -1;
}
int main(){
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int i;
    scanf("%d",&T);
    for(;T;--T){
        scanf("%d",&N);
        for(i=0;i<N;++i)
            scanf("%d",&nr[i]);
        if(N==1){
            printf("1\n");
            continue;
        }
        if(N==2){
            printf("0\n");
            continue;
        }
        if(N==3){
            if(nr[0]==1 && nr[1]==2)
                printf("1\n");
            else
                printf("0\n");
            continue;
        }
        if(nr[0]==1 || nr[0]==2)
            i=B(0);
        else
            i=C(0);
        if(i==N)
            printf("1\n");
        else
            printf("0\n");
    }
     
    fclose(stdin);
    fclose(stdout);
    return 0;
}