/* Nathan Wildenberg - C99 Basic Trie Implementation*/

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

enum {
  ALPHA = 255, // Size of the 'alphabet'
};

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 *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 *NewTrie() {
  Trie *trie = malloc(sizeof(Trie));
  trie->root = NewNode(NULL, 0);
  return 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];
    if (node->trans[ch] == NULL)
      break;
    node = node->trans[ch];
  }
  return node;
}

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];
    if (node->trans[ch] == NULL)
      node->trans[ch] = NewNode(node, ch);
    node = node->trans[ch];
  }
  ++node->apparitions;
}

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;
    }
  }
}

int QuerryWord(Trie *trie, char *word) {
  Node *node = GoToEnd(trie, word);
  if (node->level == strlen(word))
    return node->apparitions;
  else
    return 0;
}

int QuerryPrefix(Trie *trie, char *word) {
  Node *node = GoToEnd(trie, word);
  return node->level;
}

int main(int n, char *args[n]) {
  //setbuf(stdout, NULL);
  freopen("trie.in", "r", stdin);
  freopen("trie.out", "w", stdout);

  Trie *trie = NewTrie();
  int type;
  char *word;

  while (scanf("%d %s", &type, word) == 2) {
    if (type == 0)
      AddWord(trie, word);
    else if (type == 1)
      DelWord(trie, word);
    else if (type == 2)
      printf("%d\n", QuerryWord(trie, word));
    else if (type == 3)
      printf("%d\n", QuerryPrefix(trie, word));
  }
  return 0;
}