#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>

#define OP_INSERT           0
#define OP_DELETE           1
#define OP_PRINT_COUNT      2
#define OP_PRINT_LENGTH     3

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

struct trieNode {
    int count;
    std::vector<struct trieNode> neigh;
    std::vector<char> lett;
};

struct trieNode trie;

void trie_ins(trieNode &node, std::string word, int pos)
{
    if (pos == (int) word.size()) {
        node.count ++;
        return;
    }

    int i;
    for (i = 0; i < (int) node.neigh.size(); i ++) {
        if (node.lett[i] == word[pos]) {
            trie_ins(node.neigh[i], word, pos + 1);
            break;
        }
    }

    if (i == (int) node.neigh.size()) {
        node.neigh.push_back(trieNode());
        node.lett.push_back(word[pos]);
        trie_ins(node.neigh[node.neigh.size() - 1], word, pos + 1);
    }
}

bool trie_delete(trieNode &node, std::string word, int pos)
{
    if (pos == (int) word.size()) {
        node.count --;

        if (node.count == 0 && node.neigh.size() == 0) {
            return true; // Delete node from trie
        }
        else {
            return false; // Don't delete node from trie
        }
    }

    for (int i = 0; i < (int) node.neigh.size(); i ++) {
        if (node.lett[i] == word[pos]) {
            if(trie_delete(node.neigh[i], word, pos + 1) == true) {
                std::swap(node.neigh[i], node.neigh[node.neigh.size() - 1]);
                std::swap(node.lett[i], node.lett[node.lett.size() - 1]);
                node.neigh.pop_back();
                node.lett.pop_back();
                if (node.neigh.size() == 0 && node.count == 0) {
                    return true;
                }
                return false;
            }
            else {
                return false;
            }
        }
    }

    if (node.count == 0) {
        return true;
    }
    else {
        return false;
    }
}

int trie_word_count(trieNode node, std::string word, int pos)
{
    if (pos == (int) word.size()) {
        return node.count;
    }

   for (int i = 0; i < (int) node.neigh.size(); i ++) {
        if (node.lett[i] == word[pos]) {
            return trie_word_count(node.neigh[i], word, pos + 1);
        }
   }

   return 0;
}

int trie_max_prefix(trieNode node, std::string word, int pos, int lvl)
{
    if (pos == (int) word.size()) {
        return pos;
    }

    for (int i = 0; i < (int) node.neigh.size(); i ++) {
        if (node.lett[i] == word[pos]) {
            return trie_max_prefix(node.neigh[i], word, pos + 1, lvl + 1);
        }
    }

    return lvl;
 }

int main()
{
    std::string word;
    int op;

    while (f >> op >> word) {
        if (op == OP_INSERT) {
            trie_ins(trie, word, 0);
        }
        if (op == OP_DELETE) {
            trie_delete(trie, word, 0);
        }
        if (op == OP_PRINT_COUNT) {
            g << trie_word_count(trie, word, 0) << '\n';
        }
        if (op == OP_PRINT_LENGTH) {
            g << trie_max_prefix(trie, word, 0, 0) << '\n';
        }
    }

    return 0;
}