#include<fstream>
#include<cstring>
#define ch (*s - 'a')
using namespace std;

struct Trie
{
	int nrfii,cuv;
	Trie *fiu[26];
	Trie()
	{
		cuv=nrfii=0;
		memset(fiu,0,sizeof(fiu));
	}
};
Trie *T=new Trie;

void Insert(Trie *nod,char *s)
{
	if(*s==0)	//am terminat cuvantul curent
	{
		nod->cuv++;	//incrementez numarul de cuvinte
		return;
	}
	if(nod->fiu[ch]==0)	//daca nu exista fiu cu acel caracter
	{
		nod->fiu[ch]=new Trie; //creez fiul cu acel caracter
		nod->nrfii++;	//incrementez numarul de fii
	}
	Insert(nod->fiu[ch],s+1); //inserez in acel fiu urmatorul caracter din cuvant
}

bool Delete(Trie *nod,char *s)
{
	if(*s==0)	//am terminat cuvantul curent
	{
		nod->cuv--;	//decrementez numarul de cuvinte
	}
	else
	{
		if(Delete(nod->fiu[ch],s+1)==true)	//daca am eliminat fiul
		{
			nod->fiu[ch]=0;	//sterg fiul
			nod->nrfii--;	//decrementez numarul de fii
		}
	}
	if(nod->cuv==0 && nod->nrfii==0 && nod!=T)	//daca nodul nu avea cuvinte care se termina in el si nu mai are fii si nu e nici radacina
	{
		delete nod;	//sterg nodul
		return true;
	}
	return false;
}

int NrAparitii(Trie *nod,char *s)
{
	if(*s==0)	//am ajuns la finalul cuvantului
		return nod->cuv;	//returnez numarul de cuvinte care se termina in acel nod
	if(nod->fiu[ch]!=0)	//daca exista fiu cu urmatorul caracter
		return NrAparitii(nod->fiu[ch],s+1);	//merg la acel fiu
	return 0;
}

int LgPrefix(Trie *nod,char *s,short k)
{
	if(*s==0 || nod->fiu[ch]==0)	//daca am terminat cuvantul curent sau nu mai exista fiu cu urmatorul caracter
		return k;	//retunrez lungimea gasita pana aici
	return LgPrefix(nod->fiu[ch],s+1,k+1);	//altfel merg la fiul cu urmatorul caracter
}

int main()
{
	char linie[30];
	ifstream fin("trie.in");
	ofstream fout("trie.out");
	while(fin.getline(linie,30))
	{
		if(linie[0]=='0')
			Insert(T,linie+2);
		if(linie[0]=='1')
			Delete(T,linie+2);
		if(linie[0]=='2')
			fout<<NrAparitii(T,linie+2)<<"\n";
		if(linie[0]=='3')
			fout<<LgPrefix(T,linie+2,0)<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}