#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:
			// should not be the case: DO NOTHING
				break;
		}
    }
		
	input.close();
	output.close();
	
	return 0;
}