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"

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

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

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

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

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


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