#include <bits/stdc++.h>
using namespace std;

struct trieNode {
    char lett = 0;
    int isWord = 0;
    unordered_map<char, trieNode*> neigh;
};

void insertTrie(trieNode*& head, string word) {
    trieNode* aux = head;
    for (int index = 0; index < word.size(); ++index) {
        if (aux->neigh[word[index]] == NULL) {
            trieNode* newNode = new trieNode;
            newNode->lett = word[index];
            aux->neigh[word[index]] = newNode;
        }
        aux = aux->neigh[word[index]];
    }
    ++aux->isWord;
}

void deleteTrie(trieNode*& node, string word, int index) {
    if (index == word.size()) {
        --node->isWord;
        return;
    }
    deleteTrie(node->neigh[word[index]], word, index + 1);
    if (node->neigh[word[index]]->neigh.empty() && !node->neigh[word[index]]->isWord) {
        delete node->neigh[word[index]];
        node->neigh.erase(word[index]);
    }
}

int frqTrie(trieNode*& head, string word) {
    trieNode* aux = head;
    for (int index = 0; index < word.size(); ++index) {
        if (aux->neigh[word[index]] == NULL) {
            return 0;
        }
        aux = aux->neigh[word[index]];
    }
    return aux->isWord;
}

int prefix(trieNode*& head, string word) {
    int index = 0;
    trieNode* aux = head;
    for (index = 0; index < word.size(); ++index) {
        if (aux->neigh[word[index]] == NULL) {
            return index;
        }
        aux = aux->neigh[word[index]];
    }
    return index;
}

int main() {
    ifstream cin("trie.in");
    ofstream cout("trie.out");
    trieNode* head = new trieNode;
    int op;
    string word;
    while (cin >> op >> word) {
        if (op == 0) {
            insertTrie(head, word);
        } else if (op == 1) {
            deleteTrie(head, word, 0);
        } else if (op == 2) {
            cout << frqTrie(head, word) << "\n";
        } else {
            cout << prefix(head, word) << "\n";
        }
    }
}