#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");

int n,i,v[10100],j,p,ok,poz;
void p3();
void p2()
{
    if(v[poz]==2)
    {
        poz++;
        p2();
    }
    else
    if(v[poz]==1&&v[poz+2]==3)
    {
        poz+=4;
        p3();
    }
    else
        ok=0;
}
void p3()
{
    if(v[poz]==2)
        ok=1;
    else
    if(v[poz]==1&&v[poz+1]==2)
        poz+=2;
    else
    if(v[poz]==3)
    {
        poz++;
        p2();
        poz++;
        p3();
    }
    else
        ok=0;

}
int main()
{
    fin>>n;
    int m;
    for(int j=1;j<=n;j++)
    {
        fin>>m;
        for(i=1;i<=m;i++)
        {
            fin>>v[i];
        }
        ok=1;poz=1;
        if(m==1||(v[1]==1&&v[2]==2&&m==3) )
        {
            fout<<1<<'\n';
            continue;
        }

        if(v[poz]==3)
        {
            poz++;
            p2();
            poz++;
            p3();
        }
        else
        if(v[poz]==2)
        {
            poz++;
            p2();
        }
        else
        if(v[poz]==1&&v[poz+2]==3)
        {
            poz+=4;
            p3();
        }
        else
            ok=0;
        if(poz!=m)ok=0;
        fout<<ok<<'\n';

    }
    return 0;
}