#include <cstdio>
#include <cstring>
using namespace std;

int v[10001], p;
bool ok;

void B();
void C();

void B()
{
    if(v[p] == 2)
    {
        p++;
        B();
    }
    else if(v[p] == 1 && v[p + 2] == 3)
    {
        p += 4;
        C();
    }
    else
    {
        ok = 0;
        return;
    }
}

void C()
{
    if(v[p] == 1 && v[p + 1] == 2)
    {
        p += 3;
    }
    else if(v[p] == 3)
    {
        p++;
        B();
        C();
    }
    else if(v[p] == 2)
    {
        p++;
    }
    else
    {
        ok = 0;
        return;
    }
}

int main()
{
    FILE *fin, *fout;

    fin = fopen("perle.in", "r");
    fout = fopen("perle.out", "w");

    int t, n;

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

    for(int i = 1; i <= t; i++)
    {
        fscanf(fin, "%d", &n);
        memset(v, 0, sizeof(v));
        for(int i = 1; i <= n; i++)
            fscanf(fin, "%d", &v[i]);
        if(n == 1)
            fprintf(fout, "1\n");
        else
        {
            int pr = 0;
            p = 1;
            ok = 1;
            B();
            if(ok == 1 && p - 1 == n)
            {
                fprintf(fout, "1\n");
                pr = 1;
            }
            p = 1;
            ok = 1;
            C();
            if(ok == 1 && p - 1 == n)
            {
                fprintf(fout, "1\n");
                pr = 1;
            }
            if(pr == 0)
                fprintf(fout, "0\n");
        }
    }

    return 0;
}