#include <bits/stdc++.h>
#define L_ALF 26
using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");


struct trie
{
    trie *fii[L_ALF];
    int nr_ap_cuvant, nr_fii;
};


trie* aloca_mem_nod()
{
    trie *nod_nou = new trie;
    nod_nou->nr_fii = 0;
    nod_nou->nr_ap_cuvant = 0;

    for(int i = 0; i < L_ALF; i++)
    {
        nod_nou->fii[i] = NULL;
    }

    return nod_nou;
}

void adauga(trie *t, char *s)
{
    int n = strlen(s);
    int indice_litera;

    for(int i = 0; i < n - 1; i++)  // merg pana la penultima litera
    {
        indice_litera = s[i] - 'a';
        if(!t->fii[indice_litera])
        {
            t->fii[indice_litera] = aloca_mem_nod();
            t->nr_fii++;
        }
        t = t->fii[indice_litera];
    }

    indice_litera = s[n - 1] - 'a';  // ultima litera incheie cuvantul, e speciala ptr ca aici nr_ap_cuvant++
    if(!t->fii[indice_litera])
    {
        t->fii[indice_litera] = aloca_mem_nod();
        t->nr_fii++;
        t->fii[indice_litera]->nr_ap_cuvant = 1;
    }
    else
    {
        t->fii[indice_litera]->nr_ap_cuvant++;
    }

}

int nr_aparitii(trie *t, char *cuvant)
{
    int n = strlen(cuvant);
    int indice_litera;

    for(int i = 0; i < n - 1; i++)
    {
        indice_litera = cuvant[i] - 'a';
        if(t->fii[indice_litera] == NULL)
        {
            return 0;
        }

        t = t->fii[indice_litera];
    }

    indice_litera = cuvant[n - 1] - 'a';
    if(t->fii[indice_litera] == NULL || t->fii[indice_litera]->nr_ap_cuvant == 0)
    {
        return 0;
    }

    return t->fii[indice_litera]->nr_ap_cuvant;
}


int lung_prefix(trie *t, char *cuvant)
{
    int i = -1;
    int n = strlen(cuvant);
    int indice_litera;

    while(t)
    {
        i++;

        if(i == n)
            break;
        indice_litera = cuvant[i] - 'a';
        t = t->fii[indice_litera];
    }

    return i;
}

void sterge2(trie *t, char *cuvant, int i, int &stop)
{
    int n = strlen(cuvant);
    if(stop == 0)
    {
        if(i <= n - 2)
        {
            sterge2(t->fii[cuvant[i + 1] - 'a'], cuvant, i + 1, stop);

            if(stop == 0)
            {
                t->nr_fii--;
                t->fii[cuvant[i + 1] - 'a'] = NULL;
                delete t->fii[cuvant[i + 1] - 'a'];


                if(t->nr_fii >= 1)
                    stop = 1;
            }
        }
        else
        {
            if(t->nr_ap_cuvant > 1 || t->nr_fii > 0)
                {
                    t->nr_ap_cuvant--;
                    stop = 1;
                }
        }
    }
}



int main()
{
    char sir[32];
    trie *t;

    t = aloca_mem_nod();

    while(fin.getline(sir, 32))
    {
        if(sir[0] == '0')
        {
            adauga(t, sir + 2);
        }
        else
        {
            if(sir[0] == '2')
            {
                fout << nr_aparitii(t, sir + 2) << "\n";
            }
            else
            {
                if(sir[0] == '3')
                {
                    fout << lung_prefix(t, sir + 2) << "\n";
                }
                else
                {
                    if(sir[0] == '1')
                    {
                        int stop = 0;
                        sterge2(t, sir + 2, -1, stop);
                    }
                }
            }
        }
    }


    return 0;
}