#include <iostream>
#include <fstream>

using namespace std;

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

const int LMAX = 26;
char s[LMAX];

struct Trie {
    int aparitii, cuvinte;
    Trie *fiu[LMAX];
    Trie() {
        aparitii = cuvinte = 0;
        for (int i = 0; i < LMAX; i++) fiu[i] = NULL;
    }
};
Trie *radacina;

Trie *insereaza(Trie *t, char *s) {
    if (t == NULL) t = new Trie;
    t->aparitii++;
    if (s[0] == 0) t->cuvinte++;
    else t->fiu[s[0] - 'a'] = insereaza(t->fiu[s[0] - 'a'], s + 1);
    return t;
}

Trie *sterge(Trie *t, char *s) {
    t->aparitii--;
    if (s[0] == 0) t->cuvinte--;
    else t->fiu[s[0] - 'a'] = sterge(t->fiu[s[0] - 'a'], s + 1);
    if (t->aparitii == 0) {
        delete(t);
        return NULL;
    }
    return t;
}

int numar_aparitii(Trie *t, char *s) {
    if (t == NULL) return 0;
    if (s[0] == 0) return t->cuvinte;
    return numar_aparitii(t->fiu[s[0] - 'a'], s + 1);
}

int prefix_maxim(Trie *t, char *s) {
    if (t == NULL) return -1;
    if (s[0] == 0) return 0;
    return 1 + prefix_maxim(t->fiu[s[0] - 'a'], s + 1);
}


void rezolva() {
    int t;
    radacina = new Trie;
    while (f >> t) {
        f >> s;
        if (t == 0) radacina = insereaza(radacina, s);
        else if (t == 1) radacina = sterge(radacina, s);
        else if (t == 2) g << numar_aparitii(radacina, s) << '\n';
        else g << prefix_maxim(radacina, s) << '\n';
    }
}

int main() {
    rezolva();
    return 0;
}