#include<fstream>
//#include<iostream.h>
//#include<conio.h>
#include<string.h>

using namespace std;

struct nod
{int nr_ap,nr_cuv;
 nod * cuv[27];
};

nod * r;

void adauga(char s[21])
{nod * p=r;
 int i,x;
 for(i=0;i<strlen(s);i++)
    {x=s[i]-'a';
     if(r->cuv==NULL)
       {r->cuv[x]=new nod;
        r=r->cuv[x];
        }
        else
          r=r->cuv[x];
     r->nr_ap++;
     }     
} 

void sterge(char s[21])
{int i,x;
 for(i=0;i<strlen(s);i++)
    {x=s[i]-'a';
     if(r->cuv[x]!=NULL)
        r=r->cuv[x];
     r->nr_ap--;
     }   
 }

int nr_aparitii(char s[21])
{int i,x;
 for(i=0;i<strlen(s);i++)
    {x=s[i]-'a';
     if(r->cuv[x]!=NULL)
        r=r->cuv[x];
      else  return 0;
     }
 return r->nr_ap;       
 }

int prefix(char s[21])
{int i,x,gasit=1,nr=0;
 for(i=0;i<strlen(s) && gasit==1;i++)
    {x=s[i]-'a';
     if(r->cuv[x]!=NULL && r->cuv[x]->nr_ap!=0)   
        {r=r->cuv[x];
         nr++;
         }
         else  gasit=0;
     }   
 return nr;    
 }
 

int main()
{int i,x;
 char s[21];
 r->nr_ap=0;
 r->nr_cuv=0;
 for(i=0;i<27;i++)
   r->cuv[i]=NULL;
   
 ifstream f("trie.in");
 ofstream g("trie.out");  
 while(f>>x>>s)
   {if(x==0)       adauga(s);
      else
       if(x==1)    sterge(s);
        else
         if(x==2)  g<<nr_aparitii(s);
          else     g<<prefix(s);
    } 
 f.close();
 g.close();     
 //getch();
 return 0;
}