#include <fstream>
#include <cstring>
#define In "trie.in"
#define Out "trie.out"
#define ch (*s-'a')
using namespace std;
struct Trie
{
    int nr_fii;
    int nr_cuv;
    Trie *fiu[30];
    Trie()//initializari
    {
        nr_fii = 0;
        nr_cuv = 0;
        memset(fiu,0,sizeof(fiu));
    }
};

Trie *T = new Trie;
char s[30];

inline void Adauga(Trie *nod,char *s)
{
    if(*s==0)//am terminat cuvantul
    {
        nod->nr_cuv++;//incrementez numarul de cuvinte
        return ;
    }
    if(nod->fiu[ch]==NULL)//daca e nevoie sa cream un fiu
    {
        nod -> fiu[ch] = new Trie;//cream nodul
        nod -> nr_fii++;//incrementam numarul de fii
    }
    Adauga(nod -> fiu[ch],s+1);//inseram in acel fiu urmatorul caracter
}

inline bool Sterge(Trie * nod,char *s)
{
    if(*s == 0)
        nod -> nr_cuv--;//decrementez numarul de cuvinte
    else
    {
        if(Sterge(nod -> fiu[ch],s + 1)==1)//daca am eliminat  fiul
        {
            nod -> fiu[ch] = 0;//sterg fiul
            nod -> nr_fii--;//decrementez numarul de fii
        }
    }
    if(nod -> nr_fii==0 && nod -> nr_cuv==0 && nod!=T)
    {
        delete nod;
        return true;
    }
    return false;
}

inline int Aparitii(Trie *nod,char *s)
{
    if(*s==0)
        return nod -> nr_cuv;
    if(nod->fiu[ch]!=0)
        return Aparitii(nod->fiu[ch],s+1);
    return 0;
}
inline int Lg_Prefix(Trie *nod,char *s,short lg)
{
    if(*s==0 || nod -> fiu[ch]==0)//am terminat sau nu mai avem fiu
        return lg;//returnez cat am gasit
    return Lg_Prefix(nod -> fiu[ch],s+1,lg+1);
}

int main()
{
    ifstream f(In);
    ofstream g(Out);
    while(f.getline(s,30))
    {
        if(s[0]=='0')
            Adauga(T,s+2);
        if(s[0]=='1')
            Sterge(T,s+2);
        if(s[0]=='2')
            g<<Aparitii(T,s+2)<<"\n";
        if(s[0]=='3')
            g<<Lg_Prefix(T,s+2,0)<<"\n";
    }
    return 0;
}