#include <cstdio>

#define sqrInf 999999999

using namespace std;

FILE *f, *g;

int n;

int a[10009];

int simb(int len, int dr);
int simc(int len, int dr);

int simb(int len, int dr)
{
    if(len > dr)
        return sqrInf;

    if(a[len] == 2)
        return simb(len + 1, dr);

    if(a[len] == 1 && len + 4 <= dr && a[len + 2] == 3)
        return simc(len + 4, dr);

    return sqrInf;
}

int simc(int len, int dr)
{
    if(len > dr)
        return sqrInf;

    if(a[len] == 2)
        return len;

    if(a[len] == 1 && len + 2 <= dr && a[len + 1] == 2)
        return len + 2;

    if(a[len] == 3 && len + 2 <= dr)
    {
        return simc(simb(len + 1, dr) + 1, dr);
    }

    return sqrInf;
}

bool pos(int len, int dr, int cr)
{
    if(len > dr)
        return 0;

    if(cr == 1)
        return (dr == len);

    if(cr == 2)
    {
        if(a[len] == 2)
            return pos(len + 1, dr, 2);

        if(a[len] == 1 && len + 4 <= dr)
            return (a[len + 2] == 3 && pos(len + 4, dr, 3));
    }

    if(cr == 3)
    {
        if(a[len] == 2 && dr == len)
            return 1;

        if(a[len] == 1 && dr - len + 1 == 3 && a[len + 1] == 2)
            return 1;

        if(a[len] == 3)
        {
            int  ok = 0;

            if(len + 2 > dr)
                return 0;

            len ++;

            while(len <= dr && a[len] == 2)
                len ++;

            if(len > dr)
                return 0;

            //printf("%d\n", len);

            if(a[len] == 1 && len + 5 <= dr && a[len + 2] == 3)
            {
                ///len+4...dr cu CC...

                //printf("+++%d\n", simc(len + 4, dr));

                return pos(simc(len + 4, dr) + 1, dr, 3);
            }


            return ok;
        }
    }

    return 0;
}

void ansQues()
{
    f = fopen("perle.in", "r");
    g = fopen("perle.out", "w");

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

    while(t > 0)
    {
        t --;

        fscanf(f, "%d", &n);

        int i;
        for(i = 1; i <= n; i ++)
            fscanf(f, "%d", &a[i]);

        if(pos(1, n, 1) == 1)
            fprintf(g, "1\n");

        else
            if(pos(1, n, 2) == 1)
                fprintf(g, "1\n");

        else
            if(pos(1, n, 3) == 1)
                fprintf(g, "1\n");

        else
            fprintf(g, "0\n");
    }

    fclose(f);
    fclose(g);
}

int main()
{
    ansQues();

    return 0;
}