#include <stdio.h>
#include <stdlib.h>
#define CHARS 26
typedef struct nodul{
  struct nodul* fiu[CHARS];
  int nrc, nrp;
}nod;
FILE *in;

nod* adaug(nod* p, char ch){
  if(p == NULL){
    p = (nod*) malloc(sizeof(nod));
    p->nrc = 0;
    p->nrp = 1;
    int i;
    for(i = 0; i < CHARS; i++){
      p->fiu[i] = NULL;
    }
  }
  else  p->nrp++;
  if(ch != '\n'){
    p->fiu[ch - 'a'] = adaug(p->fiu[ch - 'a'], fgetc(in));
  }
  else{
    p->nrc++;
  }
  return p;
}

nod* sterg(nod* p, char ch){
  p->nrp--;
  if(ch != '\n'){
    p->fiu[ch - 'a'] = sterg(p->fiu[ch - 'a'], fgetc(in));
  }
  else{
    p->nrc--;
  }
  if(p->nrp == 0){
    free(p);
    p = NULL;
  }
  return p;
}

int apar(nod* p, char ch){
  if(ch != '\n'){
    if(p->fiu[ch - 'a'] != NULL){
      return apar(p->fiu[ch - 'a'], fgetc(in));
    }else{
      while(ch != '\n')
        ch = fgetc(in);
      return 0;
    }
  }
  else
    return p->nrc;
}

int prefix(nod* p, char ch){
  if(ch == '\n')
    return 0;
  else{
    if(p->fiu[ch - 'a'] != NULL){
      return 1 + prefix(p->fiu[ch - 'a'], fgetc(in));
    }
    else{
      while(ch != '\n')
        ch = fgetc(in);
      return 0;
    }
  }
}

int main(){
  in = fopen("trie.in", "r");
  FILE *out = fopen("trie.out", "w");
  nod* r = NULL;
  int x;
  char ch, n = fgetc(in);
  fgetc(in);
  while(n != EOF){
    ch = fgetc(in);
    x = -1;
    switch(n){
      case '0':
        r = adaug(r, ch);
        break;
      case '1':
        r = sterg(r, ch);
        break;
      case '2':
        x = apar(r, ch);
        break;
      case '3':
        x = prefix(r, ch);
        break;
    }
    if(x != -1){
      fprintf(out, "%d\n", x);
    }
    n = fgetc(in);
    fgetc(in);
  }
  fclose(in);
  fclose(out);
  return 0;
}