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

        //}
        else if(v[i]==1 and v[i+1]==2 and i+2==n)
        {
            ok=1;
            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);
        if(ok==0)
            perle(1,2);
        if(ok==0)
            perle(1,3);
        if(ok==1)
            g<<"1"<<endl;
        else
            g<<"0"<<endl;
    }
}