#include <fstream>
#include <cstring>

using namespace std;

typedef struct elem
{
	int val;
	int depth;
	int wordNumber;
	struct elem** childList;
public:
	elem(int val, int depth)
		{this->val = val; this->depth = depth; childList = new elem*[27](); wordNumber = 0;}

	~elem() {delete[] childList; childList = NULL;}
}Elem;

void Insert(int pos, int length, char word[], Elem* root);
void Delete(int pos, int length, char word[], Elem** root);
int FindWordNumber(int pos, int length, char word[], Elem* root);
int FindPrefixLength(int pos, int length, char word[], Elem* root);
void DeleteElem(Elem** root);

int main()
{
    ifstream fin;
    ofstream fout;
    fout.open("trie.out");
    fin.open("trie.in");

    int opt;
    char word[21];
    Elem* root = new Elem(-1, 0);

    while(fin >> opt >> word)
    {
    	switch(opt)
    	{
    		case 0:
    			Insert(0, strlen(word), word, root);
    			break;
    		case 1:
    			Delete(0, strlen(word), word, &root);
    			break;
    		case 2:
				fout << FindWordNumber(0, strlen(word), word, root) << "\n";
    			break;
    		case 3:
    			fout << FindPrefixLength(0, strlen(word), word, root) << "\n";
    			break;
    		default:
    			exit(1);
    	}
    }

    fin.close();
    fout.close();
    return 0;
}

void Insert(int pos, int length, char word[], Elem* root)
{
	if (pos > length - 1)
	{
		root->wordNumber ++;
	}
	else
	{
		if(root->childList[word[pos] - 'a'] == NULL)
		{
			root->childList[word[pos] - 'a'] = new Elem(word[pos] - 'a', root->depth + 1);
		}

		Insert(pos + 1, length, word, root->childList[word[pos] - 'a']);
	}
}

void Delete(int pos, int length, char word[], Elem** root)
{
	if (pos <= length - 1)
	{
		if((*root)->childList[word[pos] - 'a'] == NULL)
		{
			return;
		}
		Delete(pos + 1, length, word, &((*root)->childList[word[pos] - 'a']));
	}
	else
	{
		(*root)->wordNumber--;
	}

	DeleteElem(root);
}

void DeleteElem(Elem** root)
{
	if(root == NULL)
		return;

	if((*root)->wordNumber == 0)
	{
		bool flag = true;

		for(int i = 0; i < 26; i++)
		{
			if((*root)->childList[i] != NULL)
				flag = false;
		}

		if(flag)
		{
			delete (*root);
			(*root) = NULL;
		}
	}
}

int FindWordNumber(int pos, int length, char word[], Elem* root)
{
	if(root == NULL)
	{
		return 0;
	}

	if (pos == length)
	{
		return root->wordNumber;
	}
	else
	{
		return FindWordNumber(pos + 1, length, word, root->childList[word[pos] - 'a']);
	}
}

int FindPrefixLength(int pos, int length, char word[], Elem* root)
{
	if(root == NULL || pos > length)
	{
		return 0;
	}

	int result = 0;
	if (pos < length)
		result = FindPrefixLength(pos + 1, length, word, root->childList[word[pos] - 'a']);

	if(result != 0)
		return result;

	bool flag = false;

	for(int i = 0; i < 26; i++)
	{
		if(root->childList[i] != NULL)
			flag = true;
	}

	if(flag || root->wordNumber > 0)
		return root->depth;

	return 0;
}