#include <iostream>
#include <fstream>
#include <cstring>

#define sigma 26

using namespace std;

int op;
string s;

ifstream fi("trie.in");
ofstream fo("trie.out");

struct Trie {
	int children; // cate pozitii din cele 26 nu au valoarea NULL
	int words; // cate cuvinte se termina in nodul curent din Trie
	Trie *c[sigma];
	Trie() {
		children = words = 0;
		for (int i = 0; i < sigma; i++)
			c[i] = NULL;
	}
};

Trie * T = new Trie;

void adauga(Trie *node, int p)
{
	if (p == s.size())
	{
		node -> words++;
		return;
	}
	int letter = s[p] - 'a';
	if (node -> c[letter] == NULL)
	{
		node -> c[letter] = new Trie;
		node -> children++;
	}
	adauga(node -> c[letter], p+1);
}

bool sterge(Trie *node, int p)
{
	int letter = s[p] - 'a';
	if (p == s.size()) node -> words--;
	else
	{
		if (sterge(node -> c[letter], p + 1)) // true
		{
			node -> children--;
			node -> c[letter] = NULL;
		}
	}
	if (node -> words == 0 && node -> children == 0 && node != T)
	{
		delete node;
		return true;
	}
	return false;
}

int numarAparitii(Trie *node, int p)
{
	if (p == s.size())
		return node -> words;
	int letter = s[p] - 'a';
	if (node -> c[letter] == NULL) return 0;
	return numarAparitii(node -> c[letter], p + 1);
}

int lungimePrefix(Trie *node, int p)
{
	if (p == s.size()) return p;
	int letter = s[p] - 'a';
	if (node -> c[letter] == NULL) return p;
	return lungimePrefix(node -> c[letter], p + 1);
}

int main()
{

	/*
		0 w - adauga o aparitie a cuvantului w in lista
		1 w - sterge o aparitie a cuvantului w din lista
		2 w - tipareste numarul de aparitii ale cuvantului w in lista
		3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant
			  din lista
	*/

	while (fi >> op >> s)
	{
		switch(op)
		{
			case 0:
				adauga(T, 0);
				break;
			case 1:
				sterge(T, 0);
				break;
			case 2:
				fo << numarAparitii(T, 0) << "\n";
				break;
			case 3:	
				fo << lungimePrefix(T, 0) << "\n";
				break;
		}
	}

	fi.close();
	fo.close();

	return 0;
}