#include <fstream>

using namespace std;

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

struct Trie
{
    int cnt, nrf;
    Trie *fii[26];

    Trie()
    {
        cnt = nrf = 0;
        for(int i = 0; i < 26; ++i) fii[i] = NULL;
    }
};

Trie *t = new Trie;
char s[25], *p;

void adauga(Trie *nod)
{
    if(*p == '\0')
    {
        (nod->cnt)++;
        return;
    }

    int ch = *p - 'a';
    if(nod->fii[ch] == NULL)
    {
        nod->fii[ch] = new Trie;
        (nod->nrf)++;
    }

    p++;
    adauga(nod->fii[ch]);
}

bool sterge(Trie *nod)
{
    int ch = *p - 'a';
    if(*p == '\0') (nod->cnt)--;
    else
    {
        p++;
        if(sterge(nod->fii[ch]) == 1)
        {
            nod->fii[ch] = NULL;
            (nod->nrf)--;
        }
    }

    if(nod->cnt == 0 && nod->nrf == 0 && nod != t)
    {
        delete nod;
        return 1;
    }
    return 0;
}

int aparitii(Trie *nod)
{
    if(*p == '\0') return nod->cnt;

    int ch = *p - 'a';
    p++;
    if(nod->fii[ch] == NULL) return 0;
    return aparitii(nod->fii[ch]);
}

int prefix(Trie *nod)
{
    if(*p == '\0') return 0;

    int ch = *p - 'a';
    p++;
    if(nod->fii[ch] == NULL) return 0;
    return 1 + prefix(nod->fii[ch]);
}

int main()
{
    int op;
    while(fin >> op)
    {
        fin >> s;
        p = s;

        switch(op)
        {
            case 0: adauga(t);
                    break;
            case 1: sterge(t);
                    break;
            case 2: fout << aparitii(t) << '\n';
                    break;
            case 3: fout << prefix(t) << '\n';
                    break;
        }
    }
    fin.close(); fout.close();
    return 0;
}