#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char sir[10010];
int len,sp;
char strout[10100];

void push(char x){
    strout[sp]=x;
    sp++;
    return;
}

char pop(){
    sp--;
    return strout[sp];
}


int gen(){
    if(sir[0]=='1'){
        if(len==1){
            push('A');
            return 1;
        }else if(len==3){
            push('A');
            push('2');
            push('1');

            return 1;
        }else if(len>=5){
            push('C');
            push('A');
            push('3');
            push('A');
            push('1');

            return 1;

        }
    }else if(sir[0]=='2'){
        if(len==1){
            push('A');

            return 1;
        }else if(len>=6){
            push('B');
            push('2');

            return 1;
        }
    }else if(sir[0]=='3'){
        if(len==1){
            push('A');

            return 1;
        }else if(len>=7){
            push('C');
            push('B');
            push('3');

            return 1;
        }
    }
    return -1;
}



int main()
{   int n;
    char ch,temp;
    int i,j,k,clen;

    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);

    scanf("%d",&n);

    for(k=0;k<n;k++){
        scanf("%d",&len);
        scanf("%c",&ch);
        for(j=0;j<len;j++){
            scanf("%c%c",&sir[j],&ch);
        }
        sir[j]=0;

        j=0;
        i=0;
        sp=0;
        if(gen()==-1){
            printf("0\n");
            continue;
        }
        while(1){

            temp=pop();
            clen=len-i;
            if(temp=='1' && sir[i]=='1'){
                i++;
            }else if(temp=='2' && sir[i]=='2'){
                i++;
            }else if(temp=='3' && sir[i]=='3'){
                i++;
            }else if(temp=='A'){
                i++;
            }else if(temp=='B'){
                if(sir[i]=='1' && clen>=5){
                    push('C');
                    push('A');
                    push('3');
                    push('A');
                    push('1');
                }else if(sir[i]=='2' && clen>=6){
                    push('B');
                    push('2');
                }else{
                    printf("0\n");
                    break;
                }
            }else if(temp=='C'){
                    if(sir[i]=='1' && clen>=3){
                        push('A');
                        push('2');
                        push('1');
                    }else if(sir[i]=='2' && clen >=1){
                        push('2');
                    }else if(sir[i]=='3' && clen>=7){
                        push('C');
                        push('B');
                        push('3');
                    }else{
                        printf("0\n");
                        break;
                    }
            }else{
                printf("0\n");
                sp=0;
                break;
            }
            if(i==len){
                if(sp==0){
                    printf("1\n");
                }else{
                    printf("0\n");
                }
                break;
            }
        } //end while
    }


    return 0;
}