#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>

std::ifstream input( "trie.in" );
std::ofstream output( "trie.out" );

class Trie
{
public:
	int caracter;
	int word;
	std::list<std::pair<int,Trie*> >fii;
};

struct TrieSon : public std::binary_function< std::pair<int,Trie*>, int, bool >
{
	bool operator () ( const std::pair<int, Trie*> p, const int& c ) const
	{
		return p.first == c;
	}
};

Trie* new_trie( int c )
{
	Trie* node = new Trie();
	node->caracter = c;
	return node;
}

void add( Trie* node, std::string value, unsigned int deep )
{
	if ( value.size() == deep )
	{
		++node->word;
		return;
	}
	int poz = value[deep] - 96;
	std::list<std::pair<int,Trie*> >::iterator result = std::find_if(node->fii.begin(), node->fii.end(), std::bind2nd( TrieSon(), poz ) );
	if ( result != node->fii.end() )
	{
		add( result->second, value, ++deep );
	}
	else
	{
		node->fii.push_back( std::pair<int,Trie*>( poz, new_trie( poz ) ) );
		std::pair<int,Trie*> last = node->fii.back();
		add( last.second, value, ++deep );
	}
}

void deleteNode( Trie* node, std::string value, unsigned int deep )
{
	if ( value.size() == deep )
	{
		--node->word;
		return;
	}
	int poz = value[deep] - 96;
	std::list<std::pair<int,Trie*> >::iterator result = std::find_if(node->fii.begin(), node->fii.end(), std::bind2nd( TrieSon(), poz ) );
	if ( result->second->fii.size() < 1 )
	{
		if ( result->second->word == 1 )
		{
			delete result->second;
			node->fii.erase( result );
		}
		else
		{
			--result->second->word;
		}
	}
	else
	{
		deleteNode( result->second, value, ++deep );
	}
}

void find( Trie* node, std::string value, unsigned int deep )
{
	if ( value.size() == deep )
	{
		output << node->word << "\n";
		return;
	}
	int poz = value[deep] - 96;
	std::list<std::pair<int,Trie*> >::iterator result = std::find_if(node->fii.begin(), node->fii.end(), std::bind2nd( TrieSon(), poz ) );
	if ( result != node->fii.end() )
	{
		find( result->second, value, ++deep );
	}
	else
	{
		output << 0 << "\n";
		return;
	}
}

void findPrefix( Trie* node, std::string value, unsigned int deep )
{
	if ( value.size() == deep )
	{
		output << deep << "\n";
		return;
	}
	int poz = value[deep] - 96;
	std::list<std::pair<int,Trie*> >::iterator result = std::find_if(node->fii.begin(), node->fii.end(), std::bind2nd( TrieSon(), poz ) );
	if ( result != node->fii.end() )
	{
		findPrefix( result->second, value, ++deep );
	}
	else
	{
		output << deep << "\n";
		return;
	}
}

void printTree( Trie* node, int deep )
{
	if( node->fii.size() != 0 )
	{
		for ( std::list<std::pair<int,Trie*> >::iterator it = node->fii.begin(); it != node->fii.end(); ++it )
		{	
			for ( int i = 0; i < deep; ++i )
			{
				std::cout << " ";
			}
			std::cout << it->first << "\n";
			printTree( it->second, deep + 1 );
		}			
	}
}

void freeStructure( Trie* node )
{
	if ( node->fii.size() != 0 )
	{
		for ( std::list<std::pair<int,Trie*> >::iterator it = node->fii.begin(); it != node->fii.end(); ++it )
		{
			freeStructure( it->second );
		}
	}
	delete node;
}

int main( int argc, char* argv[] )
{
	Trie* root = new Trie;
	root->caracter = -1;
	root->word = 0;

	std::string line;
	while ( std::getline(input,line) )
	{
		int op = atoi( line.substr(0,1).c_str() );
		std::string data = line.substr(2,std::string::npos);
		switch( op )
		{
			case 0: add( root, data, 0 ); break;
			case 1: deleteNode( root, data, 0 ); break;
			case 2: find( root, data, 0 ); break;
			case 3: findPrefix( root, data, 0 ); break;
			default: break;
		}
	}
	freeStructure( root );

	input.close();
	output.close();
	return 0;
}