# include <bits/stdc++.h>

using namespace std;

string sir;

struct trie
{
    int val, sons;

    trie *son[26];

    trie()
    {
        val = sons = 0;
        for (int i = 0; i < 26; ++i) son[i] = NULL;
    }
};

trie *root;

void Add(trie *nodcrt, int poz)
{
    if (poz == sir.size())
    {
        nodcrt -> val++;
        return ;
    }

    int x = sir[poz] - 'a';

    if (nodcrt -> son[x] == NULL)
    {
        nodcrt -> son[x] = new trie;
        nodcrt -> sons++;
    }

    Add(nodcrt -> son[x], poz + 1);
}

void Erase(trie *nodcrt, int poz) {

    if (poz == sir.size()){
        nodcrt -> val--;
        return;
    }

    int x = sir[poz] - 'a';

    Erase(nodcrt -> son[x] , poz + 1);

    if (nodcrt -> son[x] -> val == 0 && nodcrt -> son[x] -> sons == 0) {
            nodcrt -> son[x] = NULL;
            nodcrt -> sons--;
    }
}

int numara(trie *nodcrt, int poz) {
    if (poz == sir.size())
        return ("%d\n", nodcrt -> val);

    int x = sir[poz] - 'a';

    if(nodcrt -> son[x] == NULL) return 0;
      else return numara(nodcrt -> son[x] , poz + 1);
}

int prefix(trie *nodcrt, int poz) {

    int x = sir[poz] - 'a';

    if (poz == sir.size() || nodcrt -> son[x] == NULL) return poz;

    return prefix(nodcrt -> son[x] , poz + 1);
}
int main ()

{
    ifstream f("trie.in");
    ofstream g("trie.out");

    int type;

    root = new trie;

    while (f >> type >> sir){

        if (type == 0) Add(root, 0);
        if (type == 1) Erase(root, 0);
        if (type == 2) g << numara(root, 0) << '\n';
        if (type == 3) g << prefix(root, 0) << '\n';

    }

    return 0;
}