#include <cstdio>

using namespace std;

FILE *f, *g;

int n;

int a[10009];

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 i, 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)
            {
                for(i = len + 4; i < dr; i ++)
                {
                    if(pos(len + 4, i, 3) && pos(i + 1, dr, 3))
                        return 1;
                }
            }


            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;
}