#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 2000005
#define INF 2140000000
using namespace std;
  
FILE*IN,*OUT;

int Type,Ans;
queue <int> Q;
char wrd[20];
struct Trie
{
	int fr,final,sons[26];
}T[MaxN];
void Add(char w[])
{
	int node=0,next;
	for(int i=0;w[i]!=0;i++)
	{
		next=T[node].sons[w[i]-'a'];
		if(next==0)
		{
			next=Q.front();
			Q.pop();
			T[node].sons[w[i]-'a']=next;
			T[next].fr++;
		}
		else T[next].fr++;
		node=next;
	}
	T[node].final++;
}
void Delete(char w[])
{
	int node=0,next;
	for(int i=0;w[i]!=0;i++)
	{
		next=T[node].sons[w[i]-'a'];
		T[next].fr--;
		if(T[next].fr==0)
			T[node].sons[w[i]-'a']=0,Q.push(next);
		node=next;
	}
}
int Common(char w[])
{
	int node=0,next;
	for(int i=0;w[i]!=0;i++)
	{
		next=T[node].sons[w[i]-'a'];
		if(T[next].fr>0)node=next;
		else return i;
	}
}
int Frequency(char w[])
{
	int node=0,next;
	for(int i=0;w[i]!=0;i++)
	{
		next=T[node].sons[w[i]-'a'];
		node=next;
	}
	return T[node].final;
}
int main()
{
    IN=fopen("trie.in","r");
    OUT=fopen("trie.out","w");
	
	for(int i=1;i<MaxN;i++)
		Q.push(i);
	while(fscanf(IN,"%d %s",&Type,wrd)!=-1)
	{
		if(Type==0)
			Add(wrd);
		else if(Type==1)
			Delete(wrd);
		else if(Type==2)
			fprintf(OUT,"%d\n",Frequency(wrd));
		else if(Type==3)
			fprintf(OUT,"%d\n",Common(wrd));
		memset(wrd,0,sizeof wrd);
	}
	return 0;
}