#include <fstream>

using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

struct trie
{
	int nrfii, nrcuv;
	trie*fii[26];

	trie()
	{
		nrfii = nrcuv = 0;
		memset(fii, 0, sizeof(fii));
	}
};

int tip;
char s[25];
trie *t;

void ins(trie*T, char*s);
int del(trie*T, char*s);
int aparitii(trie*T, char*s);
int prefix(trie*T, char*s, int k);

int main()
{
	t = new trie;
	do
	{
		fin >> tip >> s;
		switch (tip)
		{
		case 0: ins(t, s); break;
		case 1: del(t, s); break;
		case 2: fout << aparitii(t, s) << '\n'; break;
		case 3: fout << prefix(t, s, 0) << '\n'; break;
		}
	} while (!fin.eof());
	return 0;
}

void ins(trie*T, char*s)
{
	if (*s == 0)
		T->nrcuv++;
	else
	{
		if (!T->fii[*s - 'a'])
		{
			T->fii[*s - 'a'] = new trie;
			T->nrfii++;
		}
		ins(T->fii[*s - 'a'], s + 1);
	}
}

int del(trie*T, char*s)
{
	if (*s == 0) //am ajuns la sfarsit
		T->nrcuv--;
	else if (del(T->fii[*s - 'a'], s + 1)) //nu mai exista acel fiu
	{
		T->nrfii--;
		T->fii[*s - 'a'] = 0;
	}
	if (T->nrcuv == 0 && T->nrfii == 0 &&  //nu mai are rost sa exista nodul
		T != t)                              //insa nu trebuie sa stergem radacina
	{
		delete T;
		return 1;
	}
	return 0;
}

int aparitii(trie*T, char*s)
{
	if (*s == 0) //am ajuns la nodul cautat
		return T->nrcuv;
	else if (T->fii[*s-'a']) //am unde sa continui
		return aparitii(T->fii[*s - 'a'], s + 1);
	else return 0; //nu am unde sa continui, deci cuvantul nu exista
}

int prefix(trie*T, char*s, int k)
{
	if (*s == 0 || T->fii[*s - 'a'] == 0) //prefixul este exact cuvantul sau nu mai pot continua
		return k;
	return prefix(T->fii[*s-'a'], s + 1, k + 1); //maresc lg prefixului si continui sa caut
}