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

Nod* creareNod(){
    Nod* nod_nou=new Nod;
    nod_nou->nrfii=0;
    nod_nou->aparitii=0;
    nod_nou->tata=NULL;
    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->fii[litera]->tata=trie;
            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);
}
void sterge(Nod *trie,char *s){
    int n=strlen(s);
    Nod *p=trie;
    for(int i=0;i<n;i++){
        int litera=s[i]-'a';
        p=p->fii[litera];
        if(p==NULL)return; //nu exista cuv
    }
    if(p->aparitii==0)
        return; //for safety reasons

    if(p->aparitii>1){
        p->aparitii--;
        return; //doar sterg o dublura
    }
    if(p->aparitii==1 && p->nrfii>0){
        p->aparitii--; //e sufix pt un cuvant mai lung existent
        return ;
    }
    //p->ap=0, p->nrfii=0, sterg vertical pana la radacina sau pana gasesc o dublura/ un nod care mai are si alt fiu
    int i=n-1;
    while(i>=0 && p->tata!=NULL && p->nrfii==0){
        int litera=s[i]-'a';
        p->tata->nrfii--;
        p->tata->fii[litera]=NULL;
        Nod *aux=p->tata;
        delete p;

        p=aux; i--;
        if(p->aparitii>0)//dublura
            break;
    }
}
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;
}