#include <fstream>

using namespace std;
int i,l,n;
string s;
struct Trie{int nrfii,cnt;
Trie *fiu[26];
Trie()
{
  cnt=nrfii=0;
  for (i=0;i<26;i++)
    fiu[i]=0;
}
};

Trie *T=new Trie;
ifstream f("trie.in");
ofstream g("trie.out");
void adauga(Trie *nod,int i)
{
  if (i==l){
    nod->cnt++;return;
  }
  if (nod->fiu[(s[i]-'a')]==0){
    nod->fiu[s[i]-'a']=new Trie;
    nod->nrfii++;
  }
  adauga(nod->fiu[(s[i]-'a')],i+1);
}
bool del(Trie *nod,int i)
{
  if (i==l)
    nod->cnt--;
    else if (del(nod->fiu[(s[i]-'a')],i+1))
    {
      nod->fiu[(s[i]-'a')]=0;
      nod->nrfii--;
             }
   if (nod->cnt==0 && nod->nrfii==0 && nod!=T)
   {
   delete nod;
   return 1;
   }
   return 0;
}
int aparitii(Trie *nod,int i)
{
  if (i==l)
    return nod->cnt;
  if (nod->fiu[(s[i]-'a')])
     return aparitii(nod->fiu[(s[i]-'a')],i+1);
  return 0;
}
int prefix(Trie *nod,int i)
{
  if (i==l || nod->fiu[(s[i]-'a')])
    return i;
  return prefix(nod->fiu[(s[i]-'a')],i+1);
}
int main()
{
    while(f>>n>>s)
    {
      l=s.length();
      if (n==0)
        adauga(T,0);
      else if (n==1)
        del(T,0);
      else if (n==2)
        g<<aparitii(T,0)<<'\n';
      else
        g<<prefix(T,0)<<'\n';

    }
    return 0;
}