#include <fstream>
#include <vector>
#include <string>

using namespace std;

struct Trie {
    int ap = 0;  // Numărul de apariții ale cuvântului la acest nod
    vector<int> fiu = vector<int>(26, -1);  // Indici ai fiilor în vectorul de Trie-uri
};

vector<Trie> trieNodes(1);  // Vectorul care conține nodurile Trie, începe cu rădăcina

void adauga(int nod, const string& cuvant, int i) {
    if (i == cuvant.size()) {
        trieNodes[nod].ap++;
        return;
    }
    int index = cuvant[i] - 'a';
    if (trieNodes[nod].fiu[index] == -1) {
        trieNodes[nod].fiu[index] = trieNodes.size();
        trieNodes.push_back(Trie());
    }
    adauga(trieNodes[nod].fiu[index], cuvant, i + 1);
}

void sterge(int nod, const string& cuvant, int i) {
    if (i == cuvant.size()) {
        trieNodes[nod].ap--;
    } else {
        int index = cuvant[i] - 'a';
        sterge(trieNodes[nod].fiu[index], cuvant, i + 1);
        // Verificăm dacă trebuie să eliminăm referința la nodul fiu
        if (trieNodes[trieNodes[nod].fiu[index]].ap == 0 && trieNodes[trieNodes[nod].fiu[index]].fiu == vector<int>(26, -1)) {
            trieNodes[nod].fiu[index] = -1;
        }
    }
}

int aparitii(int nod, const string& cuvant, int i) {
    if (i == cuvant.size()) {
        return trieNodes[nod].ap;
    }
    int index = cuvant[i] - 'a';
    if (trieNodes[nod].fiu[index] != -1) {
        return aparitii(trieNodes[nod].fiu[index], cuvant, i + 1);
    }
    return 0;
}

int prefix(int nod, const string& cuvant, int i) {
    if (i == cuvant.size() || trieNodes[nod].fiu[cuvant[i] - 'a'] == -1) {
        return i;
    }
    return prefix(trieNodes[nod].fiu[cuvant[i] - 'a'], cuvant, i + 1);
}

int main() {
    ifstream fin("trie.in");
    ofstream fout("trie.out");
    int op;
    string c;

    while (fin >> op >> c) {
        switch (op) {
            case 0:
                adauga(0, c, 0);
                break;
            case 1:
                sterge(0, c, 0);
                break;
            case 2:
                fout << aparitii(0, c, 0) << '\n';
                break;
            case 3:
                fout << prefix(0, c, 0) << '\n';
                break;
        }
    }
    return 0;
}