#include <fstream>
#include <iostream>
#include <string.h>

using namespace std;


const char infile[] = "trie.in";
const char outfile[] ="trie.out";

struct TrieNode
{
	int info;
	short childCount;
	
	TrieNode* child[26];
	
	TrieNode()
	{
		childCount= 0;
		info = 0;
		memset(child, 0, sizeof(child));
	}
	
	~TrieNode()
	{
		for(int i = 0; i < 26; i++)
		{
			if(child[i] != NULL)
			{
				delete child[i];
			}
		}
	}
	
};


class Trie
{
public:
	void addWord(char* word);
	void removeWord(char* word);
	int getWordCount(char* word);
	int getWordPrefix(char* word);
protected:
private:
	TrieNode root;
	

};


void Trie::addWord(char* word)
{
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			n->child[word[currentLevel] - 'a'] = new TrieNode();
			n->childCount++;
		}
		
		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}
	n->info++;
	
//	cout << word << " " << n-> info << "\n";
}

void Trie::removeWord(char* word)
{
	
	TrieNode* parent = NULL;
	TrieNode* toDelete = NULL;
	int letter;
	
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			
			return;
			
		}
		
		if ( n->child[word[currentLevel] - 'a']->childCount == 1 || n->child[word[currentLevel] - 'a']->childCount == 0)
		{
			parent = n;
			toDelete = n->child[word[currentLevel] - 'a'];
			letter = word[currentLevel] - 'a';
		}
		
		n = n->child[word[currentLevel] - 'a'];
		
		currentLevel++;
	}
	n->info--;
	
	if(n->info == 0 && n->childCount == 0)
	{
		delete toDelete;
		parent->childCount--;
		parent->child[letter] = 0;
	}
	
	//cout << word << " " << n-> info << "\n";
}

int Trie::getWordCount(char* word)
{
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
			return 0;
		}
		
		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}
	
	//cout << word << " " << n-> info << "\n";
	return n->info;
}

int Trie::getWordPrefix(char* word)
{
	int length = strlen(word);
	int currentLevel = 0;
	TrieNode* n = &this->root;
	while(currentLevel != length)
	{
		if(n->child[word[currentLevel] - 'a'] == NULL)
		{
	
			return currentLevel;			
		}
		
		n = n->child[word[currentLevel] - 'a'];
		currentLevel++;
	}
	

	return currentLevel;
}

int main(int argc, char* argv[])
{
	
	fstream fin(infile, ios::in);
	fstream fout(outfile, ios::out);
	
	Trie trie;
	
	char input[30];
	
	while (fin.getline(input, 30))
	{
		
		
		short command = input[0] - '0';
		char* word = input + 2;
		
		
		
		
		switch (command)
		{
		case 0:
			//fout <<"\t" << "add" << " " << word << "\n";
			trie.addWord(word);
			
			break;
		case 1:
			//fout <<"\t" << "remove" << " " << word << "\n";
			trie.removeWord(word);
			
			break;
		case 2:
			
			//fout <<"\t" << "print" << " " << word << "\n";
			fout << trie.getWordCount(word) << "\n";
			break;
		case 3:
			
			//fout <<"\t" << "prefix" << " " << word << "\n";
			fout << trie.getWordPrefix(word) << "\n";
			break;
		}
		
		
		
	}
	
	fin.close();
	fout.close();
}