#include<fstream.h>
ifstream f("trie.in"); ofstream g("trie.out");
int op,ok,litera;
long p,nod,aparitii[2500000],x,y,z,c[2500000],fin[2500000],t[3][2500000],nr,i,n,aux,parinte[2500000],fol[2500000],change,ultim;
char s[30],t3[200];
int main()
{ n=1;
  while(f>>op)
   { f>>s;
     if(op==0)
	  { ok=1; nod=1; litera=-1;
	    while(ok)
		 { p=c[nod]; ok=0;
		   while(p)
		    { if(t3[p]==s[litera+1]&&t[1][p]!=parinte[nod]) { ok=1; fol[nod]=fol[t[1][p]]=1; litera++; nod=t[1][p]; p=0; parinte[t[1][p]]=nod; }
			  p=t[2][p];
            }
		 }
		aux=strlen(s)-1; if(litera==aux) aparitii[nod]++;
		else
		{ while(litera<aux)
		   { x=nod; n++; y=n;
		     if(c[x]==0) { nr++; c[x]=fin[x]=nr; t[1][nr]=y; t3[nr]=s[litera+1]; }
			 else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; t3[nr]=s[litera+1]; }
			 parinte[y]=x; z=x; x=y; y=z; 
			 if(c[x]==0) { nr++; c[x]=fin[x]=nr; t[1][nr]=y; t3[nr]=s[litera+1]; }
			 else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; t3[nr]=s[litera+1]; }
			 z=x; x=y; y=z; fol[x]=fol[y]=1;
			 litera++; nod=y; 
		   }
		  aparitii[nod]++;
		}
	  }
	 else if(op==1)
	  { ok=1; nod=1; litera=-1;
	    while(ok)
		 { p=c[nod]; ok=0;
		   while(p)
		    { if(t3[p]==s[litera+1]&&t[1][p]!=parinte[nod]) { ok=1; litera++; parinte[t[1][p]]=nod; nod=t[1][p]; p=0; }
			  p=t[2][p];
			}
		 }
		aparitii[nod]--;
		
		change=1;
		while(nod&&change)
		 { if(aparitii[nod]==0) 
		   { fol[nod]=0; ok=0; p=c[nod];
             while(p) 		   
		      { if(fol[t[1][p]]&&t[1][p]!=parinte[nod]) { ok=1; p=0; }
		        p=t[2][p];
		      }
			 if(ok) { fol[nod]=1; change=0; }
	         else nod=parinte[nod];
		   }
		   else change=0;
		 }
		   
	  }
	 else if(op==2)
	  { ok=1; nod=1; litera=-1; 
	    while(ok)
		 { p=c[nod]; ok=0;
		   while(p)
		    { if(t3[p]==s[litera+1]&&t[1][p]!=parinte[nod]) { ok=1; litera++; parinte[t[1][p]]=nod;  nod=t[1][p]; p=0; }
			  p=t[2][p];
		    }
		 }
		aux=strlen(s)-1;
		if(litera==aux) g<<aparitii[nod]<<"\n"; else g<<"0\n";
	  }
	 else
	  { ok=1; nod=1; litera=-1;
	    while(ok) 
		 { p=c[nod]; ok=0;
           while(p)
		    { if(t3[p]==s[litera+1]&&fol[t[1][p]]&&t[1][p]!=parinte[nod]) { ok=1; litera++; nod=t[1][p]; p=0; }
              p=t[2][p];
            }
         }
		g<<litera+1<<"\n"; 
	  }
   }
  g.close();
  return 0;
}