#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin ("perle.in");
ofstream fout("perle.out");
void rezA(), rezB(), rezC();
int i,t,n,ok,m;
char b[30300];
int c[10100];

void creaza()
{
    int nr=0;
    for(int i=0;b[i]!='\n'&&b[i]!=0;i++)
        if(b[i]!=' ')
            c[++nr]=b[i]-'0';
}

void rezB()
{
    if(i>m)
    {
        ok=1;
        return;
    }
    if(c[i]==2)
    {
        i++;
        rezB();
    }
    else
        if(c[i]==1&&c[i+2]==3)
        {
            i=i+4;
            rezC();
        }
        else
            ok=1;
}

void rezC()
{
    if(i>m)
    {
        ok=1;
        return;
    }
    if(c[i]==3)
    {
        i++;
        rezB();
        i++;
        rezC();
    }
    else
        if(c[i]==1&&c[i+1]==2&&i+2<=m)
            i+=2;
        else
            if(c[i]!=2)
                ok=1;
}

int main ()
{
    fin>>n;
    for(t=1;t<=n;t++)
    {
        fin>>m;
        fin.get();
        fin.get(b, m*3);
        creaza();
        i=1;ok=0;
        if(m==1)
        {
            fout<<"1\n";
            continue;
        }
        if(c[i]==1)
        {
            if(m==3)
                rezC();
            else
                rezB();
        }
        else
            if(c[i]==2)
                rezB();
            else
                if(c[i]==3)
                    rezC();
        if(i>m)
            ok=1;
        if(i<m)
            ok=1;
        fout<<1-ok<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}