//recursivitate indirecta
//pe baza ideii din job#874365(infoarena) ms. pt. Andrei1998
#include <fstream>
#include <vector>

unsigned B(unsigned poz, const std::vector<char> &sir);
unsigned C(unsigned poz, const std::vector<char> &sir);

int main(){
    std::ifstream fin("perle.in");
    std::ofstream fout("perle.out");

    unsigned N; fin>>N;
    while(N--){
        unsigned L; fin>>L;
        std::vector<char> input(L);
        for(unsigned i=0;i<L;++i) fin>>input[i];
        if(L==1) fout<<"1\n";
        else if( B(0,input)==L-1 || C(0,input)==L-1 ) fout<<"1\n";
        else fout<<"0\n";
    }
}

unsigned B(unsigned poz, const std::vector<char> &sir){
    if(poz>=sir.size()) return 0;
    else if(sir[poz]=='2') return B(poz+1,sir);
    else if(sir[poz]=='1'&& poz+2<sir.size() && sir[poz+2]=='3') return C(poz+4,sir);
    else return 0;
}

unsigned C(unsigned poz, const std::vector<char> &sir){
    if(poz>=sir.size()) return 0;
    else if(sir[poz]=='2') return poz;
    else if(sir[poz]=='1'){
        if(poz+2<sir.size()) return poz+2;
        else return 0;
    }
    else if(sir[poz]=='3'){
        unsigned aux=B(poz+1,sir);
        if(aux!=0) return C(aux+1,sir);
        else return 0;
    }
    else return 0;
}