#include <cstdio>

using namespace std;

#define NMAX 10005

char sir[NMAX];

bool sirValid(int st, int dr);
bool esteB(int st, int dr);
bool esteC(int st, int dr);

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

    int t;
    fscanf(fin, "%d", &t);

    while (t--) {
        int n;
        fscanf(fin, "%d%*c", &n);

        for (int i = 1; i <= n; ++i) {
            fscanf(fin, "%c%*c", &sir[i]);
        }

        fprintf(fout, "%d\n", sirValid(1, n));
    }

    return 0;
}

bool sirValid(int st, int dr)
{
    return (dr == st) || esteB(st, dr) || esteC(st, dr);
}

bool esteB(int st, int dr)
{
    if (st > dr)
        return false;

    if (sir[st] == '2') {
        return esteB(st + 1, dr);
    }
    else if (sir[st] == '1' && dr - st >= 4) {
        if (sir[st + 2] != '3')
            return false;
        return esteC(st + 4, dr);
    }
    else {
        return false;
    }
}

bool esteC(int st, int dr)
{
    if (st > dr)
        return false;

    if (sir[st] == '2') {
        return st == dr;
    }
    else if (sir[st] == '3') {
        for (int i = st + 2; i < dr; ++i) {
            bool valid = (esteB(st + 1, i) && esteC(i + 1, dr));
            if (valid)
                return true;
        }
        return false;
    }
    else {
        return (dr == st + 2) && (sir[st + 1] == '2');
    }
}