#include<bits/stdc++.h>
using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

struct Trie{
  Trie* ch[26]={0};
  int end=0, nr=0;
} *root=new Trie;

string s;


// void addT(){
//   Trie* t=root;
//   for(char c:s){
//     int i=c-'a';
//     if(t->ch[i]==0) t->ch[i]=new Trie;
//     t=t->ch[i];
//     t->nr++;rntu
//   }
//   t->end++;
// }

void addT(int i=0,Trie*t=root){
  if(i==s.size()) {
    t->end++;
    // t->nr++;
    return;
  }
  int ind=s[i]-'a';
  if(t->ch[ind]==0){
    t->ch[ind]=new Trie;
    t->nr++;
  }
  t=t->ch[ind];
  addT(i+1, t);
}

int searchT(int i=0, Trie *t=root){
  if(i==s.size()) return t->end;
  t=t->ch[s[i]-'a'];
  if(t) return searchT(1+i,t);
  return 0;
}

bool deleteT(int i=0, Trie *t=root){
  if(i==s.size()) {
    t->end--;
    // if(t->end==0 and t->nr==0) return 1;
  }
  else {
    Trie* &nx=t->ch[s[i]-'a'];
    if(deleteT(i+1,nx)){
      t->nr--;
      nx=0;
    }
  }
  if(t->nr==0 and t->end==0){
    delete t;
    return 1;
  }
  return 0;
}

int prefixT(int i=0, Trie* t=root){
  t=t->ch[s[i]-'a'];
  if(i==s.size() or !t) return 0;
  return 1+prefixT(i+1,t);
}


void afisT(Trie* t=root){
  for(int i=0;i<26;++i){
    Trie *nx=t->ch[i];
    if(nx!=0){
      cout<<char('a'+i)<<" "<<nx->nr<<"\n";
      afisT(nx);
    }
  }
}

int main(){
  int t;
  // root->nr=1;
  while(fin>>t>>s){
    switch (t) {
    case 0: addT(); break;
    case 1:
      deleteT();
      break;
    case 2:
      fout<<searchT()<<"\n";
      break;
    case 3:
      fout<<prefixT()<<"\n";
      break;
    }
  }
  // afisT();
}