#include <bits/stdc++.h>

#define LETTERS_SIZE 26

struct Trie {
   std::vector<Trie*> children{LETTERS_SIZE, nullptr};
   int count = 0;
   bool partial_word{false};

   ~Trie() {
      for (int i = 0; i < LETTERS_SIZE; ++i) {
         if (children[i]) {
            delete children[i];
         }
      }
   }

   void insert(const std::string &s, const int index = 0) {
         if (index == s.size()) {
            count++;
         } else {
            int pos = s[index] - 'a';
            if (children[pos] == nullptr) {
               children[pos] = new Trie();
            }
            children[pos]->insert(s, index + 1);
         }
         partial_word = true;
   }

   int find(const std::string &s, const int index = 0) {
      if (index == s.size()) {
         std::cout << s << " " << count << "\n";
         return count;
      }
      int pos = s[index] - 'a';
      if (!children[pos]) {
         return 0;
      }
      return children[pos]->find(s, index + 1);
   }

   void erase(const std::string &s, const int index = 0) {
      if (index == s.size()) {
         if (count > 0) {
            count--;
         }

         if (count == 0) {
            partial_word = false;
         }
         return;
      }
      int pos = s[index] - 'a';
      if (children[pos]) {
         children[pos]->erase(s, index + 1);
      }
   }

   int get_longest_prefix(const std::string &s, const int index = 0) {
      if (index == s.size()) {
         return 1;
      }

      int pos = s[index] - 'a';
      if (children[pos] && children[pos]->partial_word == true) {
         return 1 + children[pos]->get_longest_prefix(s, index + 1);
      }

      return 0;
   }

};

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

   std::string line;
   Trie* t = new Trie;

   while (std::getline(in, line)) {
      std::stringstream ss(line);

      int code;
      std::string word;
      ss >> code;
      ss >> word;

      if (code == 0) {
         t->insert(word);
      } else if (code == 1) {
         t->erase(word);
      } else if (code == 2) {
         out << t->find(word) << "\n";
      } else if (code == 3) {
        out << t->get_longest_prefix(word) << "\n";
      }    
   }

   in.close();
   out.close();
   delete t;
   return 0;
}