#include <iostream>
#include <fstream>
#include <cstring>
#define alphabet 27
using namespace std;
fstream f,g;
char cuv[26];
struct trie
{
    int cuvinte, nrFii;
    trie *urm[alphabet];
    trie ()
    {
        nrFii = cuvinte = 0;
        int i;
        for(i = 0 ; i <= alphabet ; i++)
            urm[i] = NULL;
    }
    bool operator = ( trie *a)
    {
        cuvinte = a->cuvinte;
        nrFii = a->nrFii;
        int i;
        for(i = 0 ; i <= alphabet ; i++)
            urm[i] = a->urm[i];
        return 1;
    }
};
trie *rad;
void adauga()
{
    int i;
    trie *p,*q;
    p = rad;
    for (i = 0 ; i< strlen(cuv); i++)
    {
        if ( p-> urm[cuv[i]-'a'] == NULL) // fac fiu nou
            {
                p->nrFii++;
                q = new trie;
                p->urm[cuv[i]-'a'] = q;
            }
        p = p->urm[cuv[i]-'a'];
    }
    p->cuvinte++;
}
int sterge_trie(int indice, trie *p)
{

    if (cuv[indice+1] != NULL && sterge_trie(indice+1,p->urm[cuv[indice+1] - 'a' ]))
    {
        p->nrFii--;
        p->urm[cuv[indice+1]- 'a'] = NULL;
        if (!p->nrFii && !p->cuvinte && p!=rad)
            {
                trie *q=p;
                delete q;
                return 1;
            }
        return 0;
    }
    if (cuv[indice + 1] == NULL)
    {
        p->cuvinte--;
        if (!p->nrFii && !p->cuvinte && p!=rad)
            {
                trie *q=p;
                delete q;
                return 1;
            }
    }
    return 0;
}
void sterge ()
{
    sterge_trie(0,rad -> urm[cuv[0] - 'a']);
}
int apariti()
{
    int i;
    trie *p=rad;
    for (i = 0 ; i < strlen(cuv) ; i++)
    {
        if (p->urm[cuv[i]-'a'] == NULL)
            return 0;
        p = p -> urm[cuv[i]-'a'];
    }
    return p -> cuvinte;
}
int prefix()
{
    int sol = 0;
    int i;
    trie *p=rad;
    for (i = 0 ; i < strlen(cuv) ; i++)
    {
        if (p->urm[cuv[i]-'a'] == NULL)
            return sol;
        p = p -> urm[cuv[i]-'a'];
        sol++;
    }
    return sol;
}
int main()
{
    int op;
    f.open("trie.in",ios::in);
    g.open("trie.out",ios::out);
    rad = new trie;
    while( f>>op>>cuv)
    {
        if (op == 0)
            adauga();
        else if (op == 1 )
            sterge();
        else if (op == 2 )
            g<<apariti()<<'\n';
        else // op == 3
            g<<prefix()<<'\n';
    }
    return 0;
}