#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#define character (*word - 'a')

using namespace std;

struct Trie
{
	int word, numar;
	Trie *ramura[26];

	Trie()
	{
		word = numar = 0;
		memset( ramura, 0, sizeof(ramura) );
	}
} *trieCuvant;	

void addWord(Trie *trie , char *word)
{
	if (*word == '\0')
	{
		trie->word++;
		return;
	}
	if (trie->ramura[character] == 0)
	{
		trie->ramura[character] = new Trie;
		trie->numar++;
	}
	addWord(trie->ramura[character], word+1);
}

int numberWords(Trie *trie, char *word)
{
	if (*word == '\0')
		return trie->word;
	if (trie->ramura[character] == 0)
		return 0;
	return numberWords(trie->ramura[character], word+1);
}

int numberPrefixes(Trie *trie, char *word, int k)
{
	if (*word == '\0')
		return k;
	else
	{
		if (trie->ramura[character] == 0)
			return k;
		return numberPrefixes(trie->ramura[character], word+1, k+1);
	}
}

int deleteWord (Trie *trie, char *word)
{
	if (*word == '\0')
		trie->word--;
	else if ( deleteWord(trie->ramura[character], word + 1) )
	{
		trie->ramura[character] = 0;
		trie->numar--;
	}
	if (trie->word == 0 && trie->numar == 0 &&  trie != trieCuvant)
	{
		delete trie;
		return 1;
	}
	return 0;
}

void trieFunction()
{
	trieCuvant = new Trie;

	ifstream fin("trie.in");
	ofstream fout("trie.out");

	char info[31];
	while (!fin.eof())
	{
		fin.getline(info, 40);
		switch(info[0])
		{
		case '0': addWord(trieCuvant, info+2);
				break;
		case '1': deleteWord(trieCuvant, info+2);
				break;
		case '2': fout<<numberWords(trieCuvant, info+2)<<"\n";
				break;
		case '3': fout<<numberPrefixes(trieCuvant, info+2, 0)<<"\n";
				break;
		}
		}
	fin.close();
	fout.close();
}

int main ()
{
	trieFunction();
	return 0;
}