#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// Program de Mircea Rebengiuc
// inceput pe 2021.11.12

#define MAXW 20
#define SIGMA 26
#define MAXNODE (100000 * MAXW)

struct Trie {
  struct Trie *adj[SIGMA];
  int cnt;
  int children;
};

struct Trie *trieInit(){
  struct Trie *trie = malloc(sizeof(struct Trie));// incet dar tb sa fac asa sa intru in memorie :(
  int i;

  trie->cnt = trie->children = 0;
  for( i = 0 ; i < SIGMA ; i++ )
    trie->adj[i] = NULL;

  return trie;
}

struct Trie *trieInsert( struct Trie *root, char *str ){
  int ch = (*str) - 'a';

  if( root == NULL )
    root = trieInit();

  if( !(*str) )
    root->cnt++;
  else{
    root->children -= (root->adj[ch] != NULL);
    root->adj[ch] = trieInsert(root->adj[ch], str + 1);
    root->children += (root->adj[ch] != NULL);
  }

  return root;
}

struct Trie *trieDelete( struct Trie *root, char *str ){
  int ch = (*str) - 'a';
  
  if( root == NULL )
    return NULL;

  if( !(*str) ){
    if( root->cnt )
      root->cnt--;
  }else{
    root->children -= (root->adj[ch] != NULL);
    root->adj[ch] = trieDelete(root->adj[ch], str + 1);
    root->children += (root->adj[ch] != NULL);
  }

  if( root->cnt == 0 && root->children == 0 ){
    free(root);
    root = NULL;
  }

  return root;
}

int trieCount( struct Trie *root, char *str ){
  int ch = (*str) - 'a';
  
  if( root == NULL )
    return 0;

  if( !(*str) )
    return root->cnt;

  return trieCount(root->adj[ch], str + 1);
}

int trieMaxComoonPref( struct Trie *root, char *str ){
  int ch = (*str) - 'a';
  
  if( !root || !(*str) || !(root->adj[ch]) )
    return 0;

  return 1 + trieMaxComoonPref(root->adj[ch], str + 1);
}

/*
char stack[MAXW];
int sp = 0;

void printDict( struct Trie *root ){
  int i;

  if( !root )
    return;

  stack[sp++] = '\n';
  stack[sp++] = '\0';
  for( i = 0 ; i < root->cnt ; i++ )
    fputs(stack, stdout);
  sp -= 2;

  for( i = 0 ; i < SIGMA ; i++ ){
    stack[sp++] = 'a' + i;
    printDict(root->adj[i]);
    sp--;
  }
}
*/

FILE *fin, *fout;

int main(){
  fin  = fopen("trie.in",  "r");
  fout = fopen("trie.out", "w");

  int type;
  char w[MAXW + 2];
  struct Trie *trie = NULL;// trie goala

  while( fscanf(fin, "%d %s", &type, w) == 2 ){
    switch( type ){

    case 0:
      trie = trieInsert(trie, w);
      break;

    case 1:
      trie = trieDelete(trie, w);
      break;

    case 2:
      fprintf(fout, "%d\n", trieCount(trie, w));
      break;

    case 3:
      fprintf(fout, "%d\n", trieMaxComoonPref(trie, w));
      break;
    }

    //printDict(trie);
    //printf("\n");
  }

  fclose(fin);
  fclose(fout);
  return 0;
}