#include <fstream>

using namespace std;

const int N=10005;

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

int a[N], n, i;

int B();

int C()
{
    if(i>n) return 0;
    if(a[i]==2) return 1;
    if(a[i]==3)
    {
        i++;
        if(B()) return C();
    }
    if(a[i]==1&&a[i+1]==2&&i+2<=n)
    {
        i+=3;
        return 1;
    }
    return 0;
}

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

int main()
{
    int t;
    fin>>t;
    while(t--)
    {
        fin>>n;
        for(i=1;i<=n;i++) fin>>a[i];
        i=1;
        if(n==1) fout<<"1\n";
        else if(a[1]==2||(a[1]==1&&a[3]==3&&n>=5)) fout<<B()<<"\n";
        else fout<<C()<<"\n";
    }
    fin.close();
    fout.close();
}