using namespace std;

#include <queue>
#include <fstream>
#include <bitset>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define mp make_pair

typedef pair<int,char> pc;
typedef vector< vector<pc> > VM;

#define IN  "trie.in"
#define OUT "trie.out"
#define N_MAX 1<<21 

VM A(1);
int H[N_MAX],S[N_MAX],NR[N_MAX];
int size=1,next,type;
string word; 

II void add(int nod)
{
	int poz = H[nod];
	++S[nod];
	FOR(i,0,(int)A[nod].sz()-1)
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
			{
				++NR[nod];
				return;
			}	
			add(A[nod][i].f);
			return;
		}	
	
	if(poz+1 > (int)word.sz() )
	{
		++NR[nod];
		return;
	}
	A[nod].pb( mp(++next,word[poz]) );
	if(size == next)
		A.resize(size<<=1);
	H[next] = H[nod] + 1;
	add(next);
}

II bool clear(int nod)
{
	int poz = H[nod];
	--S[nod];
	FOR(i,0,(int)A[nod].sz()-1)
	{
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
			{
				--NR[nod];
				return S[nod];
			}	
			if(!clear(A[nod][i].f) )
				A[nod][i].s = 0;
			return S[nod];
		}	
	}
	if(poz+1 > (int)word.sz() )
		--NR[nod];
	return S[nod];
}

II int querry(int nod)
{
	int poz = H[nod];
	
	FOR(i,0,(int)A[nod].sz()-1)
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
				return NR[nod];
			return querry(A[nod][i].f);
		}	
	
	if(poz+1 > (int)word.sz() )
		return NR[nod];
	return 0;
}

II int lcp(int nod)
{
	int poz = H[nod];
	
	FOR(i,0,(int)A[nod].sz()-1)
		if(A[nod][i].s == word[poz])
		{
			if(poz+1 > (int)word.sz() )
				return H[nod];
			return lcp(A[nod][i].f);
		}	
	return H[nod];
}

int main()
{
	ifstream fin("trie.in");  
	freopen(OUT,"w",stdout);
	
	for(;fin >> type >> word;)  
	{
		if(type == 0)
			add(0);
		if(type == 1)
			clear(0);
		if(type == 2)	
			printf("%d\n", querry(0) );
		if(type == 3)
			printf("%d\n", lcp(0) );
	}	
	
	return 0;
}