#include <fstream>
#include <memory>
#include <stdexcept>
#include <unordered_map>

const int ADD_WORD = 0;
const int DELETE_WORD = 1;
const int COUNT_WORD = 2;
const int GET_LONGEST_PREF = 3;

class Trie {
private:
  int count_words_having_preffix;
  int count_words_ending;
  std::unordered_map<char, std::unique_ptr<Trie>> children;

  void AddWord(const std::string &word, int pos) {
    this->count_words_having_preffix++;

    if (pos == word.size()) {
      this->count_words_ending++;
      return;
    }

    if (!children.contains(word[pos])) {
      children.emplace(word[pos], std::make_unique<Trie>());
    }

    children[word[pos]]->AddWord(word, pos + 1);
  }

  void DeleteWord(const std::string &word, int pos) {
    this->count_words_having_preffix--;

    if (pos == word.size()) {
      this->count_words_ending--;
      return;
    }

    if (!children.contains(word[pos])) {
      throw std::runtime_error("Attempt to recurse to an invalid node");
    }

    children[word[pos]]->DeleteWord(word, pos + 1);
  }

  int CountWord(const std::string &word, int pos) {
    if (pos == word.size()) {
      return this->count_words_ending;
    }

    if (!children.contains(word[pos])) {
      return 0;
    }

    return children[word[pos]]->CountWord(word, pos + 1);
  }

  int GetLongestPref(const std::string &word, int pos) {
    if (pos == word.size()) {
      return word.size();
    }

    if (!children.contains(word[pos])) {
      return pos;
    }

    if (children[word[pos]]->count_words_having_preffix == 0) {
      return pos;
    }

    return children[word[pos]]->GetLongestPref(word, pos + 1);
  }

public:
  Trie() : count_words_having_preffix{0}, count_words_ending{0} {}

  void AddWord(const std::string &word) { AddWord(word, 0); }

  void DeleteWord(const std::string &word) { DeleteWord(word, 0); }

  int CountWord(const std::string &word) { return CountWord(word, 0); }

  int GetLongestPref(const std::string &word) {
    return GetLongestPref(word, 0);
  }
};

int main() {
  std::ifstream input("trie.in");
  std::ofstream output("trie.out");

  int type;
  std::string word;
  Trie trie;

  while (input >> type >> word) {
    switch (type) {
    case ADD_WORD:
      trie.AddWord(word);
      break;

    case DELETE_WORD:
      trie.DeleteWord(word);
      break;

    case COUNT_WORD:
      output << trie.CountWord(word) << '\n';
      break;

    case GET_LONGEST_PREF:
      output << trie.GetLongestPref(word) << '\n';
      break;

    default:
      throw std::runtime_error("Unsupported operation " + std::to_string(type));
    }
  }

  input.close();
  output.close();

  return 0;
}