#include<cstdio>
int v[10001],st[10001];
void f()
    {int n,i,k,h;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    if(n==1)
        {printf("1\n");
        return ;
        }
    if(n==3&&v[1]==1&&v[2]==2)
        {printf("1\n");
        return ;
        }
    if(v[1]==2)
        {h=1;
        k=2;
        st[1]=2;
        st[2]=-2;
        }
    if(v[1]==1)
        {if(n<5||v[3]!=3)
            {printf("0\n");
            return ;
            }
        for(i=1;i<=4;i++)
            st[i]=v[i];
        k=5;
        h=4;
        }
    if(v[1]==3)
        {k=3;
        h=1;
        st[1]=3;
        st[2]=-2;
        }
    while(h<n)
        {h++;
        if(st[h]==-2)
            {if(v[h]==2)
                {if(h==n)
                    {printf("0\n");
                    return ;
                    }
                else
                    {st[h]=2;
                    st[h+1]=-2;
                    k++;
                    }
                }
            else if(v[h]==1)
                {if(h>=n-3)
                    {printf("0\n");
                    return ;
                    }
                else
                    {if(v[h+2]!=3)
                        {printf("0\n");
                        return ;
                        }
                    else
                        {st[h]=1;
                        st[h+1]=v[h+1];
                        st[h+2]=3;
                        st[h+3]=v[h+3];
                        k+=4;
                        h+=3;
                        }
                    }
                }
            else
                {printf("0\n");
                return ;
                }
            }
        if(st[h]==0)
            {if(v[h]==2)
                st[h]=2;
            else if(v[h]==1)
                {if(h>=n-1||v[h+1]!=2)
                    {printf("0\n");
                    return ;
                    }
                else
                    {st[h]=1;
                    st[h+1]=2;
                    st[h+1]=v[h+2];
                    h+=2;
                    k+=2;
                    }
                }
            else
                {st[h]=3;
                k+=2;
                st[h+1]=-2;
                }
            }
        }
    printf("1\n");
    }
int main ()
{freopen ("perle.in","r",stdin);
freopen ("perle.out","w",stdout);
int t,i;
scanf("%d",&t);
for(i=1;i<=t;i++)
    f();
return 0;
}