#include <iostream>
#include <fstream>
#include <string>
#include <vector>


typedef struct _Trie
{
	std::vector<_Trie *> son;
	int nrSons;
	int val;
	_Trie():son(std::vector<_Trie*>(26, nullptr)),
		nrSons(0),
		val(0)
	{
	}
} Trie;

Trie *root = new Trie();


void insertTrie(Trie *node, const char *s)
{
	if (*s - 'a' < 0 || *s - 'a' > 26)
	{
		node->val++;
	}
	else
	{
		if (node->son[*s - 'a'] == nullptr)
		{
			node->son[*s - 'a'] = new Trie();
			node->nrSons++;
		}

		insertTrie(node->son[*s - 'a'], s+1);
	}
}

bool deleteTrie(Trie *node, const char *s)
{
	if (*s - 'a' < 0 || *s - 'a' > 26)
	{
		node->val --;
	}
	else
	{
		if (node->son[*s - 'a'])
		{
			if (deleteTrie(node->son[*s - 'a'], s+1))
			{
				node->son[*s - 'a'] = nullptr;
				node->nrSons--;
			}
		}
	}

	if (node->nrSons == 0 && node->val <= 0 && node != root)
	{
		delete node;
		node = nullptr;
		return true;
	}

	return false;
}

int nrOfWordsInTrie(Trie *node, const char *s)
{
	if (*s - 'a' < 0 || *s - 'a' > 26)
	{
		return node->val;
	}
	else
	{
		if (node->son[*s - 'a'])
		{
			return nrOfWordsInTrie(node->son[*s - 'a'], s+1);
		}
		else
		{
			return 0;
		}
	}

	return 0;
}

int longestPrefix(Trie *node, const char *s, int length)
{
	if (*s - 'a' < 0 || *s - 'a' > 26)
	{
		return length;
	}
	else
	{
		if (node->son[*s - 'a'])
		{
			return longestPrefix(node->son[*s - 'a'], s+1, length+1);
		}
		else
		{
			return length;
		}
	}
}

int main ()
{
	std::ifstream input;
	input.open("trie.in");

	std::ofstream output("trie.out");

	std::string line;
	while (getline(input, line))
	{
		switch (line[0])
		{
		case '0':
			insertTrie(root, (line.c_str()+2));
			break;
		case '1':
			deleteTrie(root, (line.c_str()+2));
			break;
		case '2':
			output << nrOfWordsInTrie(root, (line.c_str()+2)) << "\n";
			break;
		case '3':
			output << longestPrefix(root, (line.c_str()+2), 0) << "\n";
			break;
		default:
			break;
		}
	}
	return 0;
}