#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("perle.in");
ofstream fout ("perle.out");

int n,t,i,st,v[10000];
int B();
int C();

int B()
{
    if(st>n) return 0;
    if(v[st]==2) { st++; return B(); }
    else if(v[st]==1 && v[st+2]==3) { st+=4; return C(); }
    else return 0;
}

int C()
{
    if(st>n) return 0;
    if(v[st]==2) return 1;
    else if(v[st]==1 && v[st+1]==2) return 1;
    else if(v[st]==3)
    {
        st++;
        if(!B())
            return 0;
        return C();
    }
    else return 0;
}

int main()
{
    fin>>t;
    while(t--)
    {
        st=1;
        fin>>n;
        for(i=1;i<=n;i++) fin>>v[i];
        if(n==1) fout<<1;
        else if(B()) fout<<1;
        else if(C()) fout<<1;
        else fout<<0;
        fout<<endl;
    }
    return 0;
}