#include <fstream>
#define NMax 10011
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int n, v[NMax], l, i, ind, ok, okB, okC;
void C();
void B()
{
    if (ok==1)
        return;
    if (ind>l) {
        ok=0;
        return;
    }
        
    if (v[ind]==2 && (v[ind+1]==2 || v[ind+1]==1)) {
        ++ind;
        B();
    }
    else if (v[ind]==1 && v[ind+2]==3) {
        ind+=4;
        C();
    }
}
void C()
{
    if (ok==1)
        return;
    if (ind>l) {
        ok=0;
        return;
    }
    if (v[ind]==2 && ind==l) {
        ++ind;
        ok=1;
        return;
    }
    else if (v[ind]==3 && (v[ind+1]==2 || v[ind+1]==1)) {
        ++ind;
        B();
        ++ind;
        C();
    }
    else if(v[ind]==1 && v[ind+1]==2) {
        ind+=2;
        if (ind==l) {
            ok=1;
            return;
        }
    }
}
int main()
{
    f>>n;
    for (; n--; ) {
        f>>l;
        for (i=1; i<=l; i++)
            f>>v[i];
        if (l==1)
            g<<1<<"\n";
        else {
            ok=0;
            ind=1;
            B();
            okB=ok;
            ok=0;
            ind=1;
            C();
            okC=ok;
            if(okB==1 || okC==1)
                g<<1<<"\n";
            else
                g<<0<<"\n";
        }
    }
    return 0;
}