#include <bits/stdc++.h>

using namespace std;

struct sir{
    string s;
    int l;
};

int n,ic=0;
sir a;
string s;

void eC ();

void eB(){
    //cout<<"eB: "<<ic<<'\n';
    if(a.s[s.length()]=='2' && s.length()+1<=a.l){
        s+="2";
        eB();
        return;
    } else if(a.s[s.length()]=='1' && a.s[s.length()+2]=='3' && s.length()+3<=a.l){
        s+="1A3A";
        eC();
        return;
    }
    return;
}

void eC(){
    //cout<<"eC: "<<s.length()<<'\n';
    if(a.s[s.length()]=='2' && s.length()<=a.l){
        s+='2';
        return;
    }
    else if(a.s[s.length()]=='1' && a.s[s.length()+1]=='2' && s.length()+2<=a.l){
        s+="12A";
        //cout<<a.s[ic+2]<<'\n';
        return;
    }
    else if(a.s[s.length()]=='3' && s.length()+2<=a.l){
         s+='3';
         eB();
         eC();
         return;
    }
    return;
}

bool egal(string a, string b){
    if (a.size()!=b.size()) return 0;
    else
    for (int i=0;i<a.size();i++){
        if(a[i]!=b[i] && a[i]!='A') return 0;
    }
    return 1;
}

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

void calcs(){
    eC();
    ic=0;
    bool sol = egal(s,a.s);
    //cout<<s<<'\n';
    if(!sol){
        s.clear();
        eB();
        sol = egal(s,a.s);
    }
    //cout<<s<<'\n';
    s.clear();
    fout<<sol<<'\n';
}
int main(){
    fin>>n;
    for(int i=0;i<n;i++){
        char c;
        a.s.clear();
        fin>>a.l;
        //cout<<i<<": ";
        for(int j=0;j<a.l;j++){
            fin>>c;
            a.s+=c;
        }
        if(a.l == 1){
            fout<<1<<'\n';
        }else if(a.l>=3){
            //cout<<a.s<<'\n';
            calcs();
        } else fout<<0<<'\n';
        ic=0;
    }
    //for(int i=0;i<n;i++) cout<<A[i].s<<'\n';
    return 0;
}