#include <fstream>
#include <cstring>

using namespace std;

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

const int SIGMA = 26,
          LENMAX = 20;

struct Trie
{
    int cnt,   /// numarul de aparitii ale cuvantului curent
        nrFii; /// numarul de fii ai nodului
    Trie *fiu[SIGMA + 1];
    Trie(): nrFii(0), cnt(0)
    {
        for (int i = 0; i < SIGMA; i++)
            fiu[i] = NULL;
    }
};

Trie *Rad = new Trie;
char w[LENMAX + 1];
int op;

inline int ind(char ch)
{
    return (int)(ch - 'a');
}

/// Op. 0 -> Inserarea cuvantului w in lista
void Insert(Trie *nod, char *w)
{
    if (*w == '\0')
    {
        nod->cnt++;
        return;
    }
    if (nod->fiu[ind(*w)] == NULL)
    {
        nod->fiu[ind(*w)] = new Trie;
        nod->nrFii++;
    }
    Insert(nod->fiu[ind(*w)], w + 1);
}

/// Op. 1 -> Stergerea unei aparitii a cuvantului w din lista
bool Delete(Trie *nod, char *w)
{
    if (*w == '\0')
        nod->cnt--;
    else
    if (Delete(nod->fiu[ind(*w)], w + 1))
    {
        nod->fiu[ind(*w)] = NULL;
        nod->nrFii--;
    }
    if (nod->cnt == 0 && nod->nrFii == 0 && nod != Rad)
    {
        delete nod;
        return 1;
    }
    return 0;
}

/// Op. 2 -> Numarul de aparitii ale cuvantului w in lista
int Frecv(Trie *nod, char *w)
{
    if (*w == '\0')
        return nod->cnt;
    if (nod->fiu[ind(*w)] != NULL)
        return Frecv(nod->fiu[ind(*w)], w + 1);
    return 0;
}

/// Op. 3 -> Lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista
int Prefix(Trie *nod, char *w)
{
    if (*w == '\0' || nod->fiu[ind(*w)] == NULL)
        return 0;
    return 1 + Prefix(nod->fiu[ind(*w)], w + 1);
}

int main()
{
    while (f >> op >> w)
    {
        switch(op)
        {
        case 0:
            Insert(Rad, w);
            break;
        case 1:
            Delete(Rad, w);
            break;
        case 2:
            g << Frecv(Rad, w) << '\n';
            break;
        case 3:
            g << Prefix(Rad, w) << '\n';
        }
        f.get();
    }
    f.close();
    g.close();
    return 0;
}