/* Nathan Wildenberg - C99 Trie Implementation
* For the problem: http://www.infoarena.ro/problema/trie
*/

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

enum {
  ALPHA = 26, // Size of the 'alphabet'
  WORD_LENGTH = 20 // Maximum size of the words
};

typedef struct Node {
  int apparitions; // number of words that end here
  int level; // The node's level(deepth) in the trie three
  int character; // The node's character
  int sons; // Number of non-NULL sons
  struct Node *father; // The node's father
  struct Node *trans[ALPHA]; // Pointers to the next transitions
} Node;

typedef struct Trie {
  struct Node *root;
} Trie;

// Node constructor
Node *NewNode(Node *father, int character) {
  Node *node = malloc(sizeof(Node));
  node->apparitions = 0;
  if (father != NULL) {
    node->level = father->level + 1;
    ++father->sons;
  }else
    node->level = 0;
  node->character = character;
  node->sons = 0;
  node->father = father;
  for (int i = 0; i < ALPHA; ++i)
    node->trans[i] = NULL;

  return node;
}

// Trie constructor
Trie *NewTrie() {
  Trie *trie = malloc(sizeof(Trie));
  trie->root = NewNode(NULL, 0);
  return trie;
}

// Returns the node that represents the longest prefix of 'word' in 'trie'
Node *GoToEnd(Trie *trie, char *word) {
  Node *node = trie->root;
  int length = strlen(word);
  for (int i = 0; i < length; ++i) {
    int ch = (int)word[i] - 'a';
    if (node->trans[ch] == NULL)
      break;
    node = node->trans[ch];
  }
  return node;
}

// Adds 'word' to 'trie'
void AddWord(Trie *trie, char *word) {
  Node *node = trie->root;
  int length = strlen(word);
  for (int i = 0; i < length; ++i) {
    int ch = (int)word[i] - 'a';
    if (node->trans[ch] == NULL)
      node->trans[ch] = NewNode(node, ch);
    node = node->trans[ch];
  }
  ++node->apparitions;
}

// Deletes 1 apparition of 'word' from 'trie' and then deletes empty nodes
void DelWord(Trie *trie, char *word) {
  Node *node = GoToEnd(trie, word);
  if (node->level == strlen(word)) {
    --node->apparitions;
    while (node != trie->root &&
          node->apparitions == 0 &&
          node->sons == 0) { // Empty node
      Node *father = node->father;
      father->trans[node->character] = NULL;
      --father->sons;
      free(node);
      node = father;
    }
  }
}

// Returns the number of apparitions of 'word' in 'trie'
int QuerryWord(Trie *trie, char *word) {
  Node *node = GoToEnd(trie, word);
  if (node->level == strlen(word))
    return node->apparitions;
  else
    return 0;
}

// Returns the length of the longest prefix of 'word' in 'trie'
int QuerryPrefix(Trie *trie, char *word) {
  Node *node = GoToEnd(trie, word);
  return node->level;
}

int main() {
  setbuf(stdout, NULL);
  freopen("trie.in", "r", stdin);
  freopen("trie.out", "w", stdout);

  Trie *trie = NewTrie();
  int type;
  char word[WORD_LENGTH + 5];

  while (scanf("%d %s", &type, word) == 2) {
    if (type == 0) // Query Type: Add Word
      AddWord(trie, word);
    else if (type == 1) // Query Type: Delete World
      DelWord(trie, word);
    else if (type == 2) // Query Type: Apparitions
      printf("%d\n", QuerryWord(trie, word));
    else if (type == 3) // Query Type: Prefix
      printf("%d\n", QuerryPrefix(trie, word));
  }
  return 0;
}