#include <cstdio>

using namespace std;

const int MAX_N = 10002;

int n, a[MAX_N], nr;

bool perl_a(int);
bool perl_b(int);
bool perl_c(int);

bool perl_a(int curr_pos) {
    if (curr_pos == n && nr == 0)
        return true;

    if (nr) {
        --nr;

        return perl_c(curr_pos + 1);
    }

    return false;
}

bool perl_b(int curr_pos) {
    if (a[curr_pos] == 2 && curr_pos + 1 <= n)
        return perl_b(curr_pos + 1);

    if (a[curr_pos] == 1 && a[curr_pos + 2] == 3 && curr_pos + 4 <= n)
        return perl_c(curr_pos + 4);

    return false;
}

bool perl_c(int curr_pos) {
    if (curr_pos == n && nr == 0 && a[curr_pos] == 2)
        return true;

    if (a[curr_pos] == 2) {
        --nr;

        return perl_c(curr_pos + 1);
    }

    if (a[curr_pos] == 3) {
        ++nr;

        return perl_b(curr_pos + 1);
    }

    if (a[curr_pos] == 1 && a[curr_pos + 1] == 2)
        return perl_a(curr_pos + 2);

    return false;
}

void cases() {
    if (perl_a(1)) {
        printf("1\n");

        return;
    }
    
    nr = 0;

    if (perl_b(1)) {
        printf("1\n");

        return;
    }

    nr = 0;

    if (perl_c(1)) {
        printf("1\n");

        return;
    }

    nr = 0;

    printf("0\n");
}

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

    int t;
    scanf("%d", &t);

    while (t) {
        --t;

        scanf("%d", &n);

        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        
        cases();
    }
}