#include <iostream>
#include <stack>
#include <fstream>
#include <cstring>
#define alphabet 28
using namespace std;
fstream f,g;
char cuv[26];
struct trie
{
    int cuvinte, nrFii;
    trie *urm[alphabet];
    trie ()
    {
        nrFii = 0 ;
        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()
{
    unsigned 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++;
                p->urm[cuv[i]-'a'] = new trie();
            }
        p = p->urm[cuv[i]-'a'];
    }
    p->cuvinte++;
}
void sterge ()
{
    trie *p=rad, *stiva[26];
    int lungime_stiva=0;

    stiva[lungime_stiva++]=rad;
    for (int i=0; i<strlen(cuv); i++)
    {
        p = p->urm[cuv[i]-'a'];
        stiva[lungime_stiva++]=p;
    }

    (stiva[lungime_stiva-1]->cuvinte)--;

    while (lungime_stiva>1)
    {
        --lungime_stiva;
        if (!stiva[lungime_stiva]->cuvinte && !stiva[lungime_stiva]->nrFii)
        {
            delete stiva[lungime_stiva];
            stiva[lungime_stiva-1]->urm[cuv[lungime_stiva-1]-'a']=NULL;
            --(stiva[lungime_stiva-1]->nrFii);
        }
        else break;
    }
}
int apariti()
{
    unsigned 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 if (op == 3 )
            g<<prefix()<<'\n';
    }

    return 0;
}