#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);

        fgets(sir, 2 * NMAX, fin);
        if (sir[2 * n] == '\n')
            sir[2 * n] = '\0';

        fprintf(fout, "%d\n", sirValid(0, 2 * n - 2));
    }

    return 0;
}

bool sirValid(int st, int dr)
{
    if (st == dr)
        return true;
    if (sir[st] == '3')
        return esteC(st, dr);
    else return (esteB(st, dr) || esteC(st, dr));
}

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

    if (sir[st] == '2') {
        return esteB(st + 2, dr);
    }
    else if (sir[st] == '1' && dr - st >= 8) {
        if (sir[st + 4] != '3')
            return false;
        return esteC(st + 8, 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 + 4; i < dr; i += 2) {
            bool valid = esteB(st + 2, i);
            if (valid) {
                return esteC(i + 2, dr);
            }
        }
        return false;
    }
    else {
        return (dr == st + 4) && (sir[st + 2] == '2');
    }
}