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

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

int A(int* sir) {
    sir++;
    return 1;
}

int B(int* sir) {
    int c = *sir;
    sir++;
    if (c == 2)
        return 1 + B(sir);
    else if (c == 1) {
        if (*(sir + 1) == 3) {
            sir += 3;
            return 4 + C(sir);
        }
        else 
            return -1;
    }
    else
        return -1;
}

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

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

    memcpy(sir, vect, l * sizeof(int));
    result = A(sir);
    if (l == result)
        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;
}