#include <stdio.h>
#include <string.h>

struct nod{
  nod *litera_urm[26];
  int aparitii;//numarul de aparitii al cuvantului care se termina pe poz asta
  int nrfii;//numarul de ramificari din acest nod
  nod(){
    aparitii=0;
    nrfii=0;
    memset(litera_urm,0,sizeof(litera_urm));
  }
};

nod *stiva[25];//stiva este un vector de pointeri de tip nod
int vf;

int main(){
  char buffer[30];
  FILE *fin=fopen("trie.in","r");
  FILE *fout=fopen("trie.out","w");

  int cod;
  char cuvant[25];
  nod *rad=new nod;
  nod *c,*prev;
  int n,i;
  while(!feof(fin)){
    fscanf(fin,"%[^\n]\n",buffer);
    sscanf(buffer,"%d %s",&cod,cuvant);
    switch(cod){
      case 0:{
        //adauga o aparitie in lista
        c=rad;
        n=strlen(cuvant);
        for(i=0;i<n;i++){
          //trec la urm nod
          prev=c;
          c=(c->litera_urm)[cuvant[i]-'a'];
          if(c==0)break; 
        }
        //pentru partea care nu e comuna
        for(;i<n;i++){
          c=new nod;
          prev->nrfii++;
          (prev->litera_urm)[cuvant[i]-'a']=c;
          prev=c;
        }
        c->aparitii++;
        break;      
      }

      case 1:{//sterg o aparitie (se garanteaza ca apare macar odata)
         c=rad;
         n=strlen(cuvant);
         vf=-1;
         for(i=0;i<n;i++){
           c=(c->litera_urm)[cuvant[i]-'a'];
           stiva[++vf]=c;
         }
         c->aparitii--;
         if(c->aparitii==0 && c->nrfii==0){
         //printf("cuvantul %s, mai apare acum de %d ori\n",cuvant,c->aparitii);
           //il sterg de tot
           while(vf>0 && ((stiva[vf]->nrfii) ==0)){
              //printf("sterg litera %c\n",cuvant[vf]);
              (stiva[vf-1]->litera_urm)[cuvant[vf]-'a']=0;
              stiva[vf-1]->nrfii--;
              //printf("stiva[%d-1]->nrfii=%d\n",vf,stiva[vf-1]->nrfii);
              delete stiva[vf];vf--;
           }
           if(vf==0 && ((stiva[vf]->nrfii) ==0)){
             delete stiva[vf];
              (rad->litera_urm)[cuvant[vf]-'a']=0;
             //printf("sterg litera %c\n",cuvant[vf]);
           }
         }
        break;
      }

      case 2:{//numarul de aparitii ale cuvantului w in lista
         c=rad;
         n=strlen(cuvant);
         for(i=0;i<n;i++){
           c=(c->litera_urm)[cuvant[i]-'a'];
           if(c==0){//cuvantul nu apare niciodata
             //printf("a fost comun numai pana la litera %c,inclusiv\n",cuvant[i-1]);
             fprintf(fout,"%d\n",0);
             break;
           }
         }
          if(i==n)//daca nu am iesit cu break
            fprintf(fout,"%d\n",c->aparitii);
      break; 
      }
      case 3:{//lungimea celui m lung prefix comun al lui w cu orice cuvant  din lista
         c=rad;
         n=strlen(cuvant);
         int lungime=0;
         for(i=0;i<n && ((c=(c->litera_urm)[cuvant[i]-'a'])!=0);i++){
             //printf("are litera %c comuna\n",cuvant[i]);
             lungime++;
         }
         fprintf(fout,"%d\n",lungime);
         
      break;
      }
    }
  }
  
return 0;
}