#include <iostream>
#include<fstream>
#include<string.h>

using namespace std;

ifstream f("trie.in");
ofstream g("trie.out");

struct nod
{
    int nr=0, nrfii=0;
    nod *fii[26]={0};
};

void adauga( char cuv[23], nod *p)
{
    int x;
    if (cuv[0]==NULL) { p->nr++; return;} ///am ajuns la finalul cuvantului
    else
    {
        x=cuv[0]-'a';
        if (p->fii[x]==0)
        {
            p->fii[x]= new nod;
            p->nrfii++;
        }
        adauga(strcpy(cuv,cuv+1), p->fii[x]);
    }
}

void sterge( char cuv[23], nod *p)
{
    int x;
    if(cuv[0]==NULL)
    {
        p->nr--;
        return;
    }
    else
    {   x=cuv[0]-'a';
        sterge(strcpy(cuv,cuv+1), p->fii[x]);
        if(p->fii[x]->nrfii==0 && p->fii[x]->nr==0)
        {
            delete p->fii[x];
            p->fii[x]=0;
            p->nrfii--;
        }
    }
}
int nr_aparitii(char cuv[23], nod *p)
{
    int x;
    if( cuv[0]==NULL)
        return p->nr;
    else
    {
        x=cuv[0]-'a';
        if(p->fii[x]==0) return 0;
        return nr_aparitii(strcpy(cuv,cuv+1), p->fii[x]);
    }
}
int prefix_max( char cuv[23], nod *p)
{
     int x;
     if(cuv[0]==NULL)
        return 0;
     else
     {
         x=cuv[0]-'a';
         if (p->fii[x]!=0)
            return 1+prefix_max(strcpy(cuv,cuv+1), p->fii[x]);
         else
            return 0;
     }
}
int task;
char cuv[23];
nod *G;
int main()
{
    G=new nod;
    while(f>>task)
    {
        f>>cuv;
        if(task==0) adauga(cuv,G);
        if(task==1) sterge(cuv,G);
        if(task==2) g<<nr_aparitii(cuv,G)<<'\n';
        if(task==3) g<<prefix_max(cuv,G)<<'\n';
    }

    f.close();
    g.close();
    return 0;
}