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

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

struct Trie
{
    short NrCuv=0;
    int frecventa=0;
    struct Trie *fii[26]= {0};
};



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

        ///
        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--;
        return;
    }

    Stergere(T->fii[loc(*cuvant)],cuvant+1);
    if(T->fii[loc(*cuvant)]->frecventa==0 &&  T->fii[loc(*cuvant)]->NrCuv==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)
{
  int sol=0;

    while(*cuvant!=0 && T->fii[loc(*cuvant)]!=0)
    {
        ++sol;
        T=T->fii[loc(*cuvant)];
        cuvant=cuvant+1;

    }

    return sol;
}

int n;
char cuvant[20];
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;
}