#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream f("fact.in");
ofstream g("fact.out");

char baza[256],a1[]={'1'},a2[]={'2'},a3[]={'3'},b1[]={'2B'},b2[]={'1A3AC'},c1[]={'2'},c2[]={'3BC'},c3[]={'12A'},*p,aux[256];

bool posibA(char sir[]){
    strcat(baza,a1);
    if(strstr(baza,sir)) return 1;
    else delete[] (&baza)
}

bool posibB(char sir[]){
return 1;
}
bool posibC(char sir[]){
return 1;
}

bool posib(char sir[]){
    int i;
    if(strstr(sir,baza)) return 1;
    else if(strlen(baza)>strlen(sir)) return 0;
    for(i=1;sir[i]!='1' or sir[i]!='2' or sir[i]!='3' ; i++);
    i--;
    strcpy(aux,i+sir);
    if(sir[i]=='A'){
        if(posibA(sir)) posib(sir);
        else return 0;
    }
    if(sir[i]=='B'){
        if(posibB(sir)) posib(sir);
        else return 0;
    }
    if(sir[i]=='C'){
        if(posibC(sir)) posib(sir);
        else return 0;
    }


}

int main()
{
    int n,i,x;
    f>>n;
    for(i=1;i<=n;i++){
        f>>x;
        if(x==1){ g<<1; continue; }
        char sir[x+1];
        f.get(sir,x);
        baza[0]=sir[0];
        baza[1]=NULL;
        g<<posib(sir)<<" ";
        delete[] (&sir[0],&sir[x+1]);
    }

    return 0;
}