#include <fstream>
#include <cstdio>

#define NMAX 10001

using namespace std ;

int st[2][NMAX + 10] , niv[2] , valid[2];
int T , l , v , i;

void read(int &x) {
    int sign = 1;
    char ch;
    x = 0;

    while(!isdigit(ch = getchar())) {
        if (ch == '-') {
            sign = -1;
        }

        else {
            sign = 1;
        }
    }

    do {
        x = x * 10 + ch - '0';
    } while (isdigit(ch = getchar()));
    x *= sign;
}

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

    read(T);
    while (T--) {
        read(l);
        if (l == 1) {
            read(v);
            printf("1\n");
            continue;
        }

        else {
            valid[1] = valid[0] = 1;
            niv[1] = niv[0] = 1;
            st[0][0] = 5;
            st[1][0] = 6;

            while (l--) {
                read(v);
                for (int i = 0; i < 2; i++) {
                    if (valid[i]) {
                        if (st[i][niv[i]-1] < 4) {
                            valid[i] = (st[i][--niv[i]] == v);
                            continue;
                        }

                        if (st[i][niv[i]-1] == 4) {
                            niv[i]--;
                            continue;
                        }

                        if (st[i][niv[i]-1] == 5) {
                            if (v == 3) valid[i] = 0;
                            if (v == 1) {
                                niv[i]--;

                                st[i][niv[i]++] = 6;
                                st[i][niv[i]++] = 4;
                                st[i][niv[i]++] = 3;
                                st[i][niv[i]++] = 4;
                            }

                            continue;
                        }

                        if (v == 2) niv[i]--;
                        if (v == 1) {
                            niv[i]--;

                            st[i][niv[i]++] = 4;
                            st[i][niv[i]++] = 2;
                        }

                        if (v == 3) {
                            niv[i]--;

                            st[i][niv[i]++] = 6;
                            st[i][niv[i]++] = 5;
                        }
                    }

                    if (!niv[i] && l) valid[i] = 0;
                }
            }

            printf("%d\n" , (!niv[0] && valid[0]) || (!niv[1] && valid[1]));
        }
    }

    return 0;
}