//#include "stdafx.h"
#include <fstream>
#include <string>
using namespace std;
class nod
{
public:
	int nr_cuvinte;
	int urmasi;
	nod **link;
	nod()
	{
		link = NULL;
		nr_cuvinte = 0;
		urmasi = 0;
	}	
};
class Trie
{
	nod *head;
public:
	Trie()
	{
		head = new nod;
	}
	void adaugare(string cuvant)
	{
		nod **parcurgere;
		
		if (head->link == nullptr)
		{
			head->link = new nod*[26];
			parcurgere = head->link;
			for (int i = 0; i < 26; i++)
				parcurgere[i] = nullptr;
		}
		else
			parcurgere = head->link;	
		head->urmasi++;

		int dimensiune = cuvant.size() - 1;

		for (int i = 0; i <= dimensiune; i++)
		{
			if (parcurgere[cuvant.at(i) - 97] == nullptr)
				parcurgere[cuvant.at(i) - 97] = new nod;
			parcurgere[cuvant.at(i) - 97]->urmasi++;

			if (i == dimensiune)
				parcurgere[cuvant.at(i) - 97]->nr_cuvinte++;
			else
			{
				if (parcurgere[cuvant.at(i) - 97]->link == nullptr)
				{
					parcurgere[cuvant.at(i) - 97]->link = new nod*[26];
					parcurgere = parcurgere[cuvant.at(i) - 97]->link;
					for (int i = 0; i < 26; i++)
						parcurgere[i] = nullptr;					
				}
				else
					parcurgere = parcurgere[cuvant.at(i) - 97]->link;					
			}
		}
	}
	int cautare(string cuvant)
	{
		int dim = cuvant.size() - 1;
		nod **parcurgere;
		parcurgere = head->link;
		for (int i = 0; i <= dim; i++)
		{
			if (parcurgere[cuvant.at(i) - 97] == nullptr)
				return 0;
			if (i == dim)
			{
				if (parcurgere[cuvant.at(i) - 97]->nr_cuvinte > 0)
					return parcurgere[cuvant.at(i) - 97]->nr_cuvinte;
				else
					return 0;
			}
			else
			{
				if (parcurgere[cuvant.at(i) - 97]->link == nullptr)
					return 0;
				else
					parcurgere = parcurgere[cuvant.at(i) - 97]->link;
			}
		}
	}
	int prefix(string cuvant)
	{
		int lungime = 0;
		int dim = cuvant.size() - 1;
		nod **parcurgere;
		parcurgere = head->link;
		for (int i = 0; i <= dim; i++)
		{
			if (parcurgere[cuvant.at(i) - 97] == nullptr)
				return lungime;
			else
				lungime++;			
		
			if (parcurgere[cuvant.at(i) - 97]->link == nullptr)
				return lungime;
			else
				parcurgere = parcurgere[cuvant.at(i) - 97]->link;			
		}
		return lungime;
	}
	void stergere(nod **parcurgere, string &cuvant, int litera)
	{
		static int stergere = 0;
		if (litera < cuvant.size())
		{
			this->stergere(parcurgere[cuvant.at(litera) - 97]->link, cuvant, litera + 1);
			
			//daca nodul actual e cel de pe ultima litera
			if (litera == cuvant.size() - 1)
			{
				if ((parcurgere[cuvant.at(litera) - 97]->link != nullptr) || (parcurgere[cuvant.at(litera) - 97]->nr_cuvinte>1))
				{
					stergere = 1;
					parcurgere[cuvant.at(litera) - 97]->nr_cuvinte--;
				}
				else
				{
					//cout << "\n"<<cuvant.at(litera)<<" nu are urmasi si se sterge\n";
					delete parcurgere[cuvant.at(litera) - 97];
					parcurgere[cuvant.at(litera) - 97] = nullptr;
				}
			}
			else
			{
				if (stergere == 0)
				{
					if (parcurgere[cuvant.at(litera) - 97]->urmasi > 1)
					{
						//cout << endl << cuvant.at(litera) << "  " << parcurgere[cuvant.at(litera) - 97]->urmasi;
						//parcurgere[cuvant.at(litera) - 97]->link = nullptr;
						parcurgere[cuvant.at(litera) - 97]->urmasi--;
						stergere = 1;
						//cout << endl << cuvant.at(litera) << "  " << parcurgere[cuvant.at(litera) - 97]->urmasi;
					}
					else
					{
						
						parcurgere[cuvant.at(litera) - 97]->link = nullptr;
						delete parcurgere[cuvant.at(litera) - 97];
						parcurgere[cuvant.at(litera) - 97] = nullptr;
					}
				}
				else
				{
					//cout << endl << cuvant.at(litera) << "  " << parcurgere[cuvant.at(litera) - 97]->urmasi;
					parcurgere[cuvant.at(litera) - 97]->urmasi--;
					//cout << endl << cuvant.at(litera) << "  " << parcurgere[cuvant.at(litera) - 97]->urmasi;
				}
					
			}
		}
		if (litera == 0)
			stergere = 0;
	}
	void actionare_stergere(string cuvant)
	{
		nod **parcurgere;
		parcurgere = head->link;
		int stergere = 0;
		this->stergere(parcurgere, cuvant, 0);
		//cout << endl;
	}
};
int main()
{
	Trie test;
	ifstream citire("trie.in");
	ofstream scriere("trie.out");
	while (!citire.eof())
	{
		int x;
		string cuvant;
		citire >> x >> cuvant;
		//cout << x << "   " << cuvant << endl;
		switch (x)
		{
		case 0:
			test.adaugare(cuvant);
			break;
		case 1:
			test.actionare_stergere(cuvant);
			break;
		case 2:
			scriere << test.cautare(cuvant) << "\n";
			break;
		case 3:
			scriere << test.prefix(cuvant) << "\n";
			break;
		}
	}
	citire.close();
	scriere.close();
	//cout << "\nprefix altcevac:" << test.prefix("altcevac");	
	//system("PAUSE");
	return 0;
}