#include <bits/stdc++.h>

using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
int x;
char cuv[21];

struct Trie{
  int ends, children_number;
  Trie *children['z' - 'a' + 1];

  Trie()
  {
    ends = children_number = 0;
    memset(children, 0, sizeof(children));
  }
};

Trie *T = new Trie;

void insert(Trie *node, char *s)
{
  if(!isalpha(*s))
    {
      node -> ends++;
      return;
    }
  if(node -> children[*s - 'a'] == 0)
  {
    node -> children[*s - 'a'] = new Trie;
    node -> children_number++;
  }
  insert(node -> children[*s - 'a'], s + 1);
}

bool del(Trie *node, char *s)
{
  if(!isalpha(*s))
    node -> ends--;
  else if(del(node -> children[*s - 'a'], s + 1))
    {
      node -> children[*s - 'a'] = 0;
      node -> children_number--;
    }
  if(node -> ends == 0 && node -> children_number == 0 && node != T)
    {
      delete node;
      return true;
    }
  return false;
}

int occ(Trie *node, char *s)
{
  if(!isalpha(*s))
    return node -> ends;
  if(node -> children[*s - 'a'])
    return occ(node -> children[*s - 'a'], s + 1);
  return 0;
}

int pref(Trie *node, char *s, int number)
{
  if(!isalpha(*s) || node -> children[*s - 'a'] == 0)
    return number;
  if(node -> children[*s - 'a'])
    return pref(node -> children[*s - 'a'], s + 1, number + 1);
  return 0;
}

void read()
{
  while(f>>x>>cuv)
   {
      switch(x)
      {
        case 0:
          insert(T, cuv);
          break;
        case 1:
          del(T, cuv);
          break;
        case 2:
          g<<occ(T, cuv)<<'\n';
          break;
        case 3:
          g<<pref(T, cuv, 0)<<'\n'; 
          break;
      }
   }
}

int main()
{
  read();
  return 0;
}