// Include
#include <fstream>
using namespace std;

// Definitii
#define letter (*word-'a')

// Structuri
struct trie_t
{
	int words; // Numarul de aparitii ale cuvantului curent in lista
	int sons; // Numarul de fii al nodului curent
	trie_t *son[26]; // Adresele fiilor nodului curent
	
	trie_t() // Constructorul
	{
		words = 0;
		sons = 0;
		memset(son, '\0', sizeof(son));
	}
};

// Functii
// Nodul curent | partea cuvantului ce inca mai trebuie parcursa
void insert(trie_t *node, char *word);
// Nodul curent | partea cuvantului ce inca mai trebuie parcursa | Returneaza true daca nodul curent a fost sters
bool erase(trie_t *node, char *word);
// Nodul curent | partea cuvantului ce inca mai trebuie parcursa | Returneaza numarul de aparitii ale cuvantului cautat
int query(trie_t *node, char *word);
// Nodul curent | partea cuvantului ce inca mai trebuie parcursa | adancimea parcurgerii, initializata cu 0 | Returneaza length
int prefix(trie_t *node, char *word, int length=0);

// Variabile
ifstream in("trie.in");
ofstream out("trie.out");

char word[21];
int type;

trie_t *root = new trie_t; // Radacina trie-ului

// Main
int main()
{
	while(in >> type >> word)
	{
		switch(type)
		{
			case 0: {	insert(root, word); break;						}
			case 1: {	erase(root, word); break;						}
			case 2: {	out << query(root, word) << '\n'; break;		}
			case 3: {	out << prefix(root, word) << '\n'; break;		}
		}
    }
	
	in.close();
	out.close();
	return 0;
}

void insert(trie_t *node, char *word)
{
	// Daca am ajuns la sfarsit, cresc numarul de aparitii ale cuvantului
	if(!*word)
	{
		++node->words;
		return;
	}
	
	// Daca fiul corespunzator literei curente nu exista, il creez, crescand simultan numarul de fii al nodului curent
	if(!node->son[letter])
	{
		node->son[letter] = new trie_t;
		++node->sons;
	}
	
	// Continui cu fiul corespunzator literei curente, considerand ca noul cuvant n-o mai contine
	insert(node->son[letter], word+1);
}

bool erase(trie_t *node, char *word)
{
	// Daca am ajuns la sfarsit, scad numarul de aparitii ale cuvantului
	if(!*word)
		--node->words;
	// Altfel, continui cu fiul corespunzator literei curente, considerand ca noul cuvant n-o mai contine
	else
		// Daca nodul a fost sters, sterg legaturile nodului curent cu acesta
		if(erase(node->son[letter], word+1))
		{
			--node->sons;
			node->son[letter] = '\0';
		}
	
	// Daca nodul e radacina, daca mai are fii sau daca mai sunt cuvinte ce se termina cu litera specifica lui, nu va fi sters
	if(node == root || node->sons || node->words)
		return false;
	
	// Altfel, sterg nodul
	delete node;
	return true;
}

int query(trie_t *node, char *word)
{
	// Daca am ajuns la sfarsit, returnez numarul de aparitii ale cuvantului
	if(!*word)
		return node->words;
	
	// Daca exista litera curenta, continui cu fiul corespunzator literei ei, considerand ca noul cuvant n-o mai contine
	if(node->son[letter])
		return query(node->son[letter], word+1);
	
	// Daca am ajuns pana aici, cuvantul nu apare in lista
	return 0;
}

int prefix(trie_t *node, char *word, int length)
{
	// Daca am ajuns la sfarsit sau nu exista fiul corespunzator literei cureinte, returnez adancimea curenta
	if(!*word || !node->son[letter])
		return length;
	// In caz contrar, continui cu fiul corespunzator literei curente, considerand ca noul cuvant n-o mai contine si adaugand un nivel in adancime
	return prefix(node->son[letter], word+1, length+1);
}