#include <bits/stdc++.h>

using namespace std;
ifstream in("trie.in");
ofstream out("trie.out");
string s;
int n;
struct Trie
{
    int cnt,nrnext;
    Trie *next[26];
    Trie()
    {
        cnt = nrnext = 0;
        memset(next,0,sizeof(next));
    }
};
Trie *T = new Trie;
void ins(Trie *nod, int p)
{
    if (p == n)
        nod->cnt++;
    else
    {
        if (nod->next[s[p]-'a'] == 0)
        {
            nod->nrnext++;
            nod->next[s[p]-'a'] = new Trie;
        }
        ins(nod->next[s[p]-'a'],p+1);
    }
}
int del(Trie *nod, int p)
{
    if (p == n)
        nod->cnt--;
    else if (del(nod->next[s[p]-'a'],p+1))
    {
        nod->next[s[p]-'a'] = 0;
        nod->nrnext--;
    }
    if (nod!=T && nod->nrnext == 0 && nod->cnt == 0)
    {
        delete nod;
        return 1;
    }
    return 0;
}
int ap(Trie *nod, int p)
{
    if (p == n)
        return nod->cnt;
    else
    {
        if (nod->next[s[p]-'a'] == 0)
            return 0;
        return ap(nod->next[s[p]-'a'],p+1);
    }
}
int pre(Trie *nod, int p)
{
    if (p == n || nod->next[s[p]-'a'] == 0)
        return p;
    return pre(nod->next[s[p]-'a'],p+1);
}
int main()
{
    int type;
    while (in >> type >> s)
    {
        n = s.length();
        switch (type)
        {
        case 0:
            ins(T,0);
            break;
        case 1:
            del(T,0);
            break;
        case 2:
            out << ap(T,0) << "\n";
            break;
        case 3:
            out << pre(T,0) << "\n";
            break;
        }
    }
}