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

typedef struct stack {
    char* st;
    int size;
    int index;
} stack_t;

stack_t* create(int size) {
    stack_t* stack = malloc(sizeof(stack_t));
    stack->index = 0;
    stack->size = 0;
    stack->st = malloc(size * sizeof(char));

    return stack;
}

void destroy(stack_t *stack) {
    free(stack->st);
    free(stack);
}

void push(stack_t *stack, char elem) {
    stack->st[stack->index++] = elem;
}

void addVector(stack_t *stack, char* vect, int n) {
    int i;

    for(i = n - 1; i >= 0; i--)
        push(stack, vect[i]);
}

char peek(stack_t *stack) {
    return stack->st[stack->index-1];
}

char pop(stack_t *stack) {
    stack->index--;
    return stack->st[stack->index];
}

int empty(stack_t *stack) {
    return stack->index == 0;
}

void clear(stack_t *stack) {
    while(!empty(stack))
        pop(stack);
}

int A(stack_t *stack) {
    if (empty(stack))
        return 0;

    char elem = peek(stack);
    if (elem > 3)
        return 0;

    pop(stack);
    return 1;
}

int B(stack_t *stack) {
    if (empty(stack))
        return 0;

    char elem = pop(stack);
    if (elem == 2)
        return B(stack);
    if (elem == 1)
    {
        int result = A(stack);
        if (!result)
            return 0;
        
        elem = pop(stack);
        if (elem != 3)
            return 0;

        result = A(stack);
        if (!result)
            return 0;
        
        return C(stack);
    }

    return 0;
}

int C(stack_t *stack) {
    if (empty(stack))
        return 0;

    char elem = pop(stack);
    if (elem == 2)
        return 1;

    if (elem == 1) {
        elem = pop(stack);
        if (elem != 2)
            return 0;

        return A(stack);
    }

    if (elem == 2) {
        int result = B(stack);
        if (!result)
            return 0;

        return C(stack);
    }

    return 0;
}

int tryParse(int n, char *vect) {
    int result;
    stack_t *stack= create(n);

    addVector(stack, vect, n);

    result = A(stack);
    if (result == 1)
        if (empty(stack))
            return 1;
    clear(stack);
    addVector(stack, vect, n);

    result = B(stack);
    if (result == 1)
        if (empty(stack))
            return 1;
    clear(stack);
    addVector(stack, vect, n);

    result = C(stack);
    if (result == 1)
        if (empty(stack))
            return 1;
    destroy(stack);

    return 0;
}

int main() 
{
    FILE* f = fopen("perle.in", "r");
    FILE* g = fopen("perle.out", "w");

    int teste;
    int i, j, l;
    fscanf(f, "%d", &teste);
    char *vect;

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

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

    fclose(f);
    fclose(g);
    return 0;
}