#include <stdio.h>

int n,l;
int a[10001];

int tb(int i);
int tc(int i);

int tb(int i)
{
    for (; i<l; i++)
        if (a[i]!=2) break;
    if (i==l)
        return 0;
    if (l < i+5)
        return 0;
    if (a[i]!=1 || a[i+2]!=3)
        return 0;
    return tc(i+4);
}

int tc(int i)
{
    if (a[i]==2)
        return i+1;
    if (a[i]==1)
    {
        if (l < i+3)
            return 0;
        if (a[i+1]==2)
         return i+3;
    }

    i=tb(i+1);
    if (i==l || i==0)
        return 0;
    return tc(i);
}


int test()
{
    if (l==1)
        return 1;

    if (a[0]==1)
    {
        if (l==3 && a[1]==2)
            return 1;
        if (l>=5 && a[2]==3)
         return (tc(4) == l);
    }
    if (a[0]==2)
        return (tb(0)==l);

    return(tc(0)==l);
}

int main()
{
    int i,j;
    FILE *fin, *fout;
    fin=fopen("perle.in", "r");
    fout=fopen("perle.out", "w");
    fscanf(fin,"%d",&n);
    for (i=0;i<n;i++)
    {
        fscanf(fin, "%d", &l);
        for (j=0;j<l;j++)
            fscanf(fin, "%d", &a[j]);
        fprintf(fout, "%d\n", test());
    }
    return 0;
}