#include<stdio.h>
#include<string.h>
int n,l,len,ok;
char sol[10001],v[10001];
char tA[4][2]={"0","1","2","3"},tB[4][6]={"00000","1A3AC","2B","0000"},tC[4][4]={"000","12A","2","3BC"};

void inlocuieste(int p,char s[])
{
    int l=strlen(s);
    for(int i=len-1;i>p;i--)
    {
        sol[i+l-1]=sol[i];
    }
    strncpy(sol+p,s,l);
    len+=l-1;
}

int rezolva()
{
    for(int i=0;i<len;i++)
    {
        if(sol[i]<='C' && sol[i]>='A')
        switch(sol[i])
        {
            case 'A': inlocuieste(i,tA[v[i]-'0']);
                      break;
            case 'B': if(v[i]!=3)
                      inlocuieste(i,tB[v[i]-'0']);
                      else
                      return 0;
                      break;
            case 'C': inlocuieste(i,tC[v[i]-'0']);

        }
    }
    if(strcmp(v,sol)==0)
    return 1;
    return 0;
}

void citire()
{
    freopen("perle.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d ",&l);
        memset(v,0,sizeof(v));
        for(int j=0;j<l;j++)
        {
            scanf("%c ",&v[j]);
        }
        if(l==1)
        {
            printf("1\n");
            continue;
        }
        ok=0;
        for(char j='A';j<='C' && !ok;j++)
        {
            memset(sol,0,sizeof(sol));
            sol[0]=j;
            len=1;
            ok=rezolva();
        }
        printf("%d\n",ok);
    }
}

int main()
{
    freopen("perle.out","w",stdout);
    citire();
    return 0;
}