#include <stdio.h>
#define LMAX 10000

// A -> 1 | 2 | while3
// B -> 2B | 1A3AC
// C -> 2 | 3BC | 12A
#define NONE 0
#define B 1
#define C 2
int n;

int set_solve() {
    int n, a[LMAX];
    int i, Cleft = 0, next;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    if (n == 1)
        return 1;
    else {
        i = 0;
        if (a[i] == 1) {
            next = C;
            if (a[i+2] != 3)
                 return 0;
            i += 4;
        }
        else if (a[i] == 2) {
            next = B;
            i++;
        }
        else {
            next = B, Cleft++;
            i++;
        }
        while (next || Cleft) {
            if (next) {
                if (next == B) {
                    if (a[i] == 1) {
                        next = C;
                        if (a[i+2] != 3)
                             return 0;
                        i += 4;
                    }
                    else if (a[i] == 2) {
                        next = B, ++i;
                    }
                    else
                         return 0;
                }
                else if (next == C) {
                    if (a[i] == 1) {
                        next = NONE;
                        if (a[i+1] != 2)
                             return 0;
                        i += 3;
                    }
                    else if (a[i] == 2) {
                        next = NONE, i++;
                    }
                    else {
                        next = B, i++, Cleft++;
                    }
                }
            }
            else if (Cleft) {
                if (a[i] == 1) {
                    next = NONE;
                    if (a[i+1] != 2)
                        return 0;
                    i += 3;
                }
                else if (a[i] == 2) {
                    next = NONE, i++;
                }
                else {
                    next = B, i++, Cleft++;
                }
                Cleft--;
            }
        }
        //printf("%d\n", i);
        if (i != n)
            return 0;
        return 1;
    }
}

int main() {
    int i;
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        printf("%d\n", set_solve());
    return 0;
}