#include<fstream>
using namespace std;
int v1[10000],l,k;
int check_C();
int check_B()
{
    if(v1[k]==2)
    {
    if(k+6<=l)
    {
        k++;
        return check_B();
    }
    else return 0;
    }
    if(v1[k]==1&&v1[k+2]==3)
    {
        if(k+5<=l)
        {
            k+=4;
            return check_C();
        }
        else return 0;
    }
}
int check_C()
{
    if(v1[k]==2)
    {
    if(k+1==l)
        return 1;
     else return 0;
    }
    if(v1[k]==1&&v1[k+1]==2)
    {
        if(k+3==l)
            return 1;
        else return 0;
    }
    if(v1[k]==3)
    {
    k++;
    int ok1=check_B(),ok2=check_C();
    if(ok1&&ok2)
        return 1;
    else return 0;
    }

}
int check()
{
    k=0;
    if(l==1)
        return 1;
    if(l==2||l==4)
        return 0;
    if(l==3)
        if(v1[0]==1&&v1[1]==2)
        return 1;
        else return 0;
    if(v1[0]==1)
    {
    if(v1[2]==3)
    {
        k=4;
        return check_C();
    }
     else
        return 0;
    }
    if(v1[0]==2)
    {
        k++;
        return check_B();
    }
    if(v1[k]==3)
    {
        k++;
        int ok1=check_B(),ok2=check_C();
        if(ok1&&ok2)
            return 1;
        else return 0;
    }

}
int main()
{
    fstream f("perle.in", ios::in), g("perle.out", ios::out);
    int i,n,j;
    f>>n;
    for(i=0;i<n;i++)
    {
        f>>l;
        for(j=0;j<l;j++)
            f>>v1[j];
        g<<check()<<"\n";
    }

f.close();
g.close();
return 0;
}