#include <cstdio>

using namespace std;
char s[50005],sol[10005];
int l,n;
void reset (){
    for (int i=0;i<=n;i++)
        sol[i]=0;
}
int verif (int pas){
    int i;
    if (l>n)
        return 0;
    else if (pas==n+1)
        return 1;
    else if (sol[pas]=='1' || sol[pas]=='2' || sol[pas]=='3'){
        if (sol[pas]==s[pas])
            return verif (pas+1);
        else return 0;
    }
    else if (sol[pas]=='A')
        return verif (pas+1);
    else if (sol[pas]=='B'){
        if (s[pas]=='2'){
            l++;
            for (i=l-1;i>=pas+1;i--)
                sol[i+1]=sol[i];
            sol[pas+1]='B';
            return verif (pas+1);
        }
        else if (s[pas]=='1'){
            l=l+4;
            for (i=l-4;i>=pas+1;i--)
                sol[i+4]=sol[i];
            sol[pas+1]=sol[pas+3]='A';
            sol[pas+2]='3';
            sol[pas+4]='C';
            return verif (pas+1);
        }
        else return 0;
    }
    else if (sol[pas]=='C'){
        if (s[pas]=='2')
            return verif (pas+1);
        else if (s[pas]=='1'){
            l=l+2;
            for (i=l-2;i>=pas+1;i--)
                sol[i+2]=sol[i];
            sol[pas+1]='2';
            sol[pas+2]='A';
            return verif (pas+1);
        }
        else if (s[pas]=='3'){
            l=l+2;
            for (i=l-2;i>=pas+1;i--)
                sol[i+2]=sol[i];
            sol[pas+1]='B';
            sol[pas+2]='C';
            return verif (pas+1);
        }
    }
    return 0;
}
int main()
{
    FILE *fin=fopen ("perle.in","r");
    FILE *fout=fopen ("perle.out","w");
    int t,i,x;
    fscanf (fin,"%d",&t);
    for (;t;t--){
        //if (t==3)
          //  printf ("a");
        fscanf (fin,"%d ",&n);
        //printf ("%d ",n);
        if (n==1){
            fscanf (fin,"%d",&x);
            fprintf (fout,"1\n");
            continue;
        }
        fgets (s+1,50005,fin);
        for (i=1;i/2+1<=n;i++)
            s[i/2+1]=s[i];
        reset();
        l=1;
        sol[1]='B';
        if (verif (1)==1){
            fprintf (fout,"1\n");
            continue;
        }
        l=1;
        reset();
        sol[1]='C';
        if (verif (1)==1){
            fprintf (fout,"1\n");
            continue;
        }
        fprintf (fout,"0\n");
    }
    return 0;
}