#include <iostream>
#include <fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
void Bila_B(int);
void Bila_C(int);
int N,lg,Elemente[10004],indicator;

void Bila_B(int pozitie)
{
    if(pozitie<=lg)
    {
    if(Elemente[pozitie]==1&&Elemente[pozitie+2]==3)
     Bila_C(pozitie+4);
    else
    if(Elemente[pozitie]==2)
    Bila_B(pozitie+1);
    else g<<0<<'\n';
    }
    else g<<0<<'\n';
}

void Bila_C(int loc)
{
    if(loc<=lg)
    {

    if(Elemente[loc]==1&&Elemente[loc+1]==2)
    {
        if(loc+2==lg&&indicator==0) g<<1<<'\n';
        else g<<0<<'\n';
    }
    else
    if(Elemente[loc]==2)
    {
        if(loc==lg||lg-loc==indicator)  g<<1<<'\n';
        else g<<0<<'\n';
    }
    else
    if(Elemente[loc]==3)
    {
        indicator++;
        Bila_B(loc+1);
    }
    else g<<0<<'\n';

    } else g<<0<<'\n';

}

int main()
{
    f>>N;
    for(int i=1;i<=N;i++)
    {
    f>>lg;
    for(int j=1;j<=lg;j++) f>>Elemente[j];
    indicator=0;
    if(Elemente[1]==1&&Elemente[3]==3)  Bila_C(5);
    else
    if(Elemente[1]==1&&Elemente[2]==2)
    {
        if(3==lg) g<<1<<'\n';
        else g<<0<<'\n';
    }
    else
    if(Elemente[1]==2)
    {
         if(lg>1) Bila_B(2);
        else
        {
            if(lg==1) g<<1<<'\n';
            else g<<0<<'\n';
        }
    }
    else
    if(Elemente[1]==3)
    { indicator++; Bila_B(2); }
    else g<<0<<'\n';

    }
    return 0;
}