#include <vector>
#include <fstream>
using namespace std;
typedef pair<int,char> pc;
vector< vector<pc> >  A(110000);
int S[1<<20],NR[1<<20];
int size=1,next,type;
string word; 

inline void add(int nod,int poz)
{
	++S[nod];
	if(poz+1 > (int)word.size() )
	{
		++NR[nod];
		return;
	}
	for(int i=0;i<=(int)A[nod].size()-1;++i)
		if(A[nod][i].second == word[poz] /*|| A[nod][i].second + 30 == word[poz]*/)
		{
			A[nod][i].second = word[poz];
			add(A[nod][i].first,poz+1);
			return;
		}	
	A[nod].push_back( make_pair(++next,word[poz]) );
	add(next,poz+1);
}

inline bool clear(int nod,int poz)
{
	--S[nod];
	if(poz+1 > (int)word.size() )
	{
		--NR[nod];
		return S[nod];
	}	
	for(int i=0;i<=(int)A[nod].size()-1;++i)
		if(A[nod][i].second == word[poz])
		{
			if(!clear(A[nod][i].first,poz+1) )
			{
				A[nod][i].second -= 30;
				A[nod][i].second = A[nod][i].second;
			}
			return S[nod];
		}	
	return S[nod];
}

inline int querry(int nod,int poz)
{
	if(poz+1 > (int)word.size())
		return NR[nod];
	for(int i=0;i<=(int)A[nod].size()-1;++i)
		if(A[nod][i].second == word[poz])
			return querry(A[nod][i].first,poz+1);
	return 0;
}

inline int lcp(int nod,int poz)
{
	for(int i=0;i<=(int)A[nod].size()-1;++i)
		if(A[nod][i].second == word[poz])
			if(poz+1>(int)word.size())
				return poz;
			else
				return lcp(A[nod][i].first,poz+1);
	return poz;
}
int main()
{
	ifstream fin("trie.in");  
	ofstream fout("trie.out");
	for(;fin>>type>>word;)  
	{
		if(type==0)
			add(0,0);
		else
			if(type==1)
				clear(0,0);
			else
				if(type==2)	
					fout<<querry(0,0)<<"\n";
				else	
					fout<<lcp(0,0)<<"\n";
	}
}