#include <fstream>
#include <string>
#include <stack>

const int SIGMA = 26;

class Trie
{
private:

  int numWords;
  int numChildren;

  Trie* father;
  Trie* children[SIGMA];

  static std::stack<Trie*> tries;
  static Trie* current;

public:

  Trie(Trie* father = nullptr)
  {
    this->numWords = 0;
    this->numChildren = 0;

    this->father = father;

    for (int i = 0; i < SIGMA; i++)
      this->children[i] = nullptr;
  }

  void add(std::string word, int pos)
  {
    Trie::current = this;

    while (pos < word.size())
    {
        if (Trie::current->children[word[pos] - 'a'] == nullptr)
        {
            Trie::current->children[word[pos] - 'a'] = new Trie(current);
            Trie::current->numChildren++;
        }

        Trie::current = Trie::current->children[word[pos] - 'a'];
        pos++;
    }

    current->numWords++;
  }

  void remove(std::string word, int pos)
  {
    Trie::current = this;
    Trie::tries.push(Trie::current);

    while (pos < word.size())
    {
        Trie::current = Trie::current->children[word[pos] - 'a'];

        Trie::tries.push(Trie::current);
        pos++;
    }

    Trie::current->numWords--;

    while (!Trie::tries.empty())
    {
        if (pos > 0 && Trie::tries.top()->numWords == 0 && Trie::tries.top()->numChildren == 0)
        {
            Trie::tries.top()->father->numChildren--;
            Trie::tries.top()->father->children[word[pos - 1] - 'a'] = nullptr;

            delete Trie::tries.top();
        }

        Trie::tries.pop();
        pos--;
    }
  }

  int count(std::string word, int pos)
  {
    Trie::current = this;

    while (pos < word.size())
    {
        if (Trie::current->children[word[pos] - 'a'] == nullptr)
        {
            return 0;
        }

        Trie::current = current->children[word[pos] - 'a'];
        pos++;
    }

    return Trie::current->numWords;
  }

  int prefix(std::string word, int pos)
  {
    Trie::current = this;

    while (pos < word.size())
    {
        if (Trie::current->children[word[pos] - 'a'] == nullptr)
        {
            return pos;
        }

        Trie::current = Trie::current->children[word[pos] - 'a'];
        pos++;
    }

    return word.size();
  }
};

std::stack<Trie*> Trie::tries;
Trie* Trie::current;

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

  Trie* trie = new Trie();

  int type;
  std::string w;

  while (in >> type >> w)
  {
    if (type == 0)
      trie->add(w, 0);
    else if (type == 1)
      trie->remove(w, 0);
    else if (type == 2)
      out << trie->count(w, 0) << '\n';
    else
      out << trie->prefix(w, 0) << '\n';
  }

  return 0;
}