#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int B(int* sir);
int C(int* sir);

int B(int* sir) {
    if (*sir == 2) {
        sir++;
        return 1 + B(sir);
    }

    if (*sir == 1 && *(sir + 2) == 3) {
            sir += 4;
            return 4 + C(sir);
    }
    
    return -1;
}

int C(int* sir) {
    if (*sir == 2) {
        sir++;
        return 1;
    }

    if (*sir == 1 && *(sir + 1) == 2) {
        sir += 3;
        return 3;
    }

    if (*sir == 3) {
        sir++;
        int result = B(sir);
        return 1 + result + C(sir);
    }

    return -1;
}

int tryParse(int l, int* vect) {
    int result;
    int *sir = malloc(l * sizeof(int));

    if (l == 1)
        return 1;
    

    memcpy(sir, vect, l * sizeof(int));
    result = B(sir);
    if (l == result)
        return 1;


    memcpy(sir, vect, l * sizeof(int));
    result = C(sir);
    if (l == result)
        return 1;

    
    return 0;
}

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

    int teste;
    int i, j, l;
    scanf("%d", &teste);
    int *vect;

    for (i = 0; i < teste; i++) {
        scanf("%d", &l);
        vect = malloc (l * sizeof(int));
        for (j = 0; j < l; j++) {
            scanf("%d", &vect[j]);
        }

        printf("%d\n", tryParse(l, vect));
        free(vect);
    }

    return 0;
}