#include<fstream>
using namespace std;
FILE *g=fopen("perle.out","w");

int i,j,n,m,a[10002],l;
int rez2(int);
int rez3(int);
int rez2(int i)
{
    while(a[i]==2&&i<=m)
        i++;
        if(a[i]==1&&a[i+2]==3)
            return rez3(i+4);
        else
            return 0;
}
int rez3(int i)
{
    if(a[i]==2)
        return i;
    else
        if(a[i]==1&&a[i+1]==2)
            return i+2;
        else
            if(a[i]==3)
            {
                int x=rez2(i+1);
                if(x!=0)
                    return rez3(x+1);
                else
                    return 0;
            }
            else
                return 0;
}
int main()
{
    FILE *f=fopen("perle.in","r");
    fscanf(f,"%d",&n);
    while(n--)
    {
        fscanf(f,"%d",&m);
        for(i=1;i<=m;i++)
            fscanf(f,"%d",&a[i]);
        if(m==1||(a[1]==1&&a[2]==2&&m==3))
            fprintf(g,"1\n");
        else
        if(m==2||(m==3&&(a[1]!=1||a[2]!=2)))
            fprintf(g,"0\n");
        else
        {
            if(a[1]==2||a[1]==1)
                {if(rez2(1)==m)
                    fprintf(g,"1\n");
                else
                    fprintf(g,"0\n");
                }
            else
                if(a[1]==3)
                {
                    if(rez3(1)==m)
                        fprintf(g,"1\n");
                    else
                        fprintf(g,"0\n");
                }
        }
    }
    return 0;
}