//stergere recursiva
#include <fstream>
using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");
struct Nod{
    int nrfii,aparitii;
    Nod *fii[26];
} *radacina;

Nod* creareNod(){
    Nod* nod_nou=new Nod;
    nod_nou->nrfii=0;
    nod_nou->aparitii=0;
    for(int i=0;i<26;i++)
        nod_nou->fii[i]=NULL;
    return nod_nou;
}

void adauga(Nod *trie,char *s){
    if(*s!=0){
        int litera=*s-'a';
        if(trie->fii[litera]==NULL){
            trie->fii[litera]=creareNod();
            trie->nrfii++; //litera noua
        }
        adauga(trie->fii[litera],s+1); //trec la urm litera
    }
    else trie->aparitii++; //retin nr de aparitii la terminarea cuvantului
}
void elib(Nod *&trie){
    if(trie){
        for(int i=0;i<26;i++)
            if(trie->fii[i])
                elib(trie->fii[i]);
        delete trie;
        trie=NULL;
    }
}
int query(Nod *trie,char *s){
    if(*s==0)
        return trie->aparitii; //sfarsitul cuv
    int litera=*s-'a';
    if(trie->fii[litera]==NULL) //nu exista cuv cerut
        return 0;
    return query(trie->fii[litera],s+1);
}
int prefix(Nod *trie,char *s){
    if(*s==0) //final cuv
        return 0;
    int litera=*s-'a';
    if(trie->fii[litera]==NULL) //nu mai exista litere comune, final prefix
        return 0;
    return 1+prefix(trie->fii[litera],s+1);
}
int sterge(Nod *trie,char *s){
    if(*s==0)
        trie->aparitii--; //final de cuvant
    else{
        int litera=*s-'a';
        if(sterge(trie->fii[litera],s+1)){
            trie->nrfii--;
            trie->fii[litera]=NULL;
        }
    }

    if(trie->aparitii==0 && trie->nrfii==0 && trie!=radacina){
        delete trie;
        return 1;
    }
    return 0;
}
int t;
char s[30];
int main(){
    radacina=creareNod();
    while(fin>>t>>s){
        if(t==0)
            adauga(radacina,s);
        else if(t==1)
            sterge(radacina,s);
        else if(t==2)
            fout<<query(radacina,s)<<"\n";
        else fout<<prefix(radacina,s)<<"\n";
    }
    elib(radacina);
    return 0;
}