#include <iostream>
#include <fstream>
using namespace std;

ofstream fo("trie.out");
ifstream fi("trie.in");

struct Trie
{
    int NrCuv=0,frecventa=0;
    struct Trie *fii[27]= {0};
};



int loc(char cuvant)
{
    return cuvant-'a';
}
void Adauga(Trie *T,char *cuvant)
{
    if(*cuvant==0)
    {
        T->NrCuv++;
        T->frecventa++;
        ///
        return;
    }
    if(T->fii[loc(*cuvant)]==0)
    {
        T->fii[loc(*cuvant)]=new Trie;

    }
    T->frecventa++;

    Adauga(T->fii[loc(*cuvant)],cuvant+1);
}

void Stergere(Trie *T, char *cuvant)
{
    if(*cuvant==0)
    {
        T->NrCuv--;
        T->frecventa--;
        return;
    }

    Stergere(T->fii[loc(*cuvant)],cuvant+1);
    if(T->fii[loc(*cuvant)]->frecventa==0)
    {
        delete T->fii[loc(*cuvant)];
        T->fii[loc(*cuvant)]=0;
        T->frecventa--;
    }


}

int nrAparitii(Trie *T, char *cuvant)
{
    if(*cuvant==0)
        return T->NrCuv;

    if(T->fii[loc(*cuvant)]==0)
        return 0;

    return nrAparitii(T->fii[loc(*cuvant)],cuvant+1);
}

int PrefixMax(Trie *T, char *cuvant)
{
    if( *cuvant==0 || T->fii[loc(*cuvant)]==0)
        return 0;


    return 1+PrefixMax(T->fii[loc(*cuvant)],cuvant+1);

}

int n;
char cuvant[30];
Trie *T; /// se aloca memorie pt o structura de tip Trie la adresa T

int main()
{

    T=new Trie;
    while(fi>>n)
    {
        fi>>cuvant;

        if(n==0) Adauga(T,cuvant);
        if(n==1)Stergere(T,cuvant);
        if(n==2)fo<<nrAparitii(T,cuvant)<<'\n';
        if(n==3)fo<<PrefixMax(T,cuvant)<<'\n';
    }
    fo.close();
    fi.close();
    return 0;
}