#include <cstdio>
using namespace std;
int v[10002];
bool checkb(int x,int nr,int oof);
bool checkc(int x,int nr,int oof);
bool check(int x,int nr)
{
    if(v[x]==1)
    {
        if(nr==1)
            return 1;
        if(nr==3&&v[x+1]==2)
            return 1;
        if(nr>=5)
            if(v[x+2]==3)
                return checkc(x+4,nr-4,0);
        return 0;
    }
    if(v[x]==2)
    {
        if(nr==1)
            return 1;
        return checkb(x+1,nr-1,0);
    }
    if(v[x]==3)
    {
        if(nr==1)
            return 1;
        if(nr>3)
            return checkb(x+1,nr-1,1);
        return 0;
    }
}
bool checkb(int x,int nr,int oof)
{
        if(nr>1&&v[x]==2)
            return checkb(x+1,nr-1,oof);
        if(nr>=5)
            if(v[x]==1&&v[x+2]==3)
                return checkc(x+4,nr-4,oof);
        return 0;

}
bool checkc(int x,int nr, int oof)
{
    if(!oof)
    {
        if(nr==1&&v[x]==2)
            return 1;
        if(nr>3&&v[x]==3)
            return checkb(x+1,nr-1,1);
        if(nr==3)
            if(v[x]==1&&v[x+1]==2)
                return 1;
        return 0;
    }
    if(v[x]==2)
        return checkc(x+1,nr-1,oof-1);
    if(v[x]==3)
        return checkb(x+1,nr-1,oof+1);
    if(v[x]==1&&nr>=3)
        if(v[x+1]==2)
            return checkc(x+3,nr-3,oof-1);
    return 0;
}
int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int n,m,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&m);
        for(j=1;j<=m;j++)
            scanf("%d",&v[j]);
        printf("%d\n",check(1,m));
        for(j=1;j<=m;j++)
            v[j]=0;
    }

    return 0;
}