#include <fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int v[10002],n,ok,ii,okk;
void perle(int i, int x, int y)
{
    if(ok==1)
        return;
    if(i>n)
        return;
    if(x==1)
    {
        if(i==n)
        {
            ok=1;
            return;
        }
        else if(y==1)
        {
            okk=1;
            ii=i;
            return;
        }
    }
    else if(x==2)
    {
        if(v[i]==2 and v[i+1]!=3)
        {
            perle(i+1,2,y);
        }
        else if(v[i]==1 and v[i+2]==3)
        {
            perle(i+4,3,y);
        }
        else
            return;
    }
    else if(x==3)
    {
        if(v[i]==2)
        {
            if(i==n)
            {
                ok=1;
                return;
            }
            else if(y==1)
            {
                okk=1;
                ii=i;
                return;
            }
        }
        else if(v[i]==3 and v[i+1]!=3)
        {
            perle(i+1,2,1);
            if(okk=1)
            {
                okk=0;
                perle(ii+1,3,y);
            }
            else
                return;
        }
        else if(v[i]==1 and v[i+1]==2)
        {
            if(i+2==n)
            {
                ok=1;
                return;
            }
            else if(y==1)
            {
                okk=1;
                ii=i+2;
                return;
            }
        }
        else
            return;
    }
}
int main()
{
    int m,i,j;
    f>>m;
    for(j=1;j<=m;j++)
    {
        f>>n;
        ok=0;
        for(i=1;i<=n;i++)
        {
            f>>v[i];
        }
        perle(1,1,0);
        if(ok==0)
            perle(1,2,0);
        if(ok==0)
            perle(1,3,0);
        if(ok==1)
            g<<"1"<<endl;
        else
            g<<"0"<<endl;
    }
}