#include <stdio.h>
#define MAXN 10000
int n, err, p;
char v[MAXN+5];
inline void match(char ch){
    if(ch==v[p]){
        p++;
    }else{
        err=0;
    }
}
void C();
void B(){
    if(err==1){
        if(v[p]=='1'){
            p++;
            p++;
            match('3');
            p++;
            C();
        }else{
            match('2');
            B();
        }
    }
}
void C(){
    if(err==1){
        if(v[p]=='1'){
            p++;
            match('2');
            p++;
        }else if(v[p]=='2'){
            p++;
        }else{
            match('3');
            B();
            C();
        }
    }
}
int main(){
    int T, t, f, i;
    FILE *fin, *fout;
    fin=fopen("perle.in", "r");
    fout=fopen("perle.out", "w");
    fscanf(fin, "%d ", &T);
    for(t=0; t<T; t++){
        fscanf(fin, "%d", &n);
        for(i=0; i<n; i++){
            fgetc(fin);
            v[i]=fgetc(fin);
        }
        for(i=n; i<=MAXN; i++){
            v[i]='\0';
        }
        f=0;
        if(n==1){
            f=1;
        }
        p=0;
        err=1;
        B();
        if(p!=n){
            err=0;
        }
        f|=err;
        p=0;
        err=1;
        C();
        if(p!=n){
            err=0;
        }
        f|=err;
        fprintf(fout, "%d\n", f);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}