#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fstream>


#define ALPH_SIZE 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')


using namespace std;


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


typedef struct tn {
	int value;
	tn *children[ALPH_SIZE];
} TrieNode, *ATrieNode;


typedef struct trie {
	TrieNode *root;
} Trie, *ATrie;


TrieNode *createTrieNode(){
	ATrieNode node = (ATrieNode)malloc(sizeof(TrieNode));
	if(!node){
		printf("ERROR: Unable to create a new trie node!\n");
		return NULL;
	}

	node->value = 0;
	int i;
	for(i = 0; i < ALPH_SIZE; ++i){
		node->children[i] = NULL;
	}
	return node;
}


ATrie init(){
	ATrie t = (ATrie)malloc(sizeof(Trie));
	if(!t){
		printf("ERROR: Unable to create a new trie!\n");
		return NULL;
	}
	t->root = createTrieNode();

	return t;
}


void insertKey(ATrie t, char key[]){

	int level;
	int length = strlen(key);
	int indx;
	ATrieNode node;

	node = t->root;

	for(level = 0; level < length; ++level){
		indx = CHAR_TO_INDEX(key[level]);
		if(!node->children[indx])
			node->children[indx] = createTrieNode();

		node = node->children[indx];
	}
	node->value++;
}

int countKey(ATrie t, char key[]){

	int level;
	int length = strlen(key);
	int indx;
	ATrieNode node = t->root;

	for(level = 0; level < length; ++level){
		indx = CHAR_TO_INDEX(key[level]);
		if(!node->children[indx])
			return 0;
		node = node->children[indx];
	}

	if(node && node->value > 0){
		return node->value;
	}

	return 0;
}



int countPrefixKey(ATrie t, char key[]){

	int count = 0;
	int level;
	int length = strlen(key);
	int indx;
	ATrieNode node = t->root;

	for(level = 0; level < length; ++level){
		indx = CHAR_TO_INDEX(key[level]);
		if(!node->children[indx])
			return count;
		count++;
		node = node->children[indx];
	}
	return count;
}



bool isWord(ATrieNode node){
	return (node->value != 0);
}



bool isLeafNode(ATrieNode node){
	int i;
	for(i = 0; i < ALPH_SIZE; ++i){
		if(node->children[i])
			return false;
	}
	return true;
}

bool deleteKey(ATrieNode node, char key[], int level){
	
	int len = strlen(key);
	if(len <= 0 || !node)
		return false;

	if(level == len){
		node->value--;

		if(isLeafNode(node))
			return true;

		return false;
	}

	else{
		int indx = CHAR_TO_INDEX(key[level]);

		if(deleteKey(node->children[indx], key, level+1)){
			free(node->children[indx]);
			node->children[indx] = NULL;

			return(!isWord(node) && isLeafNode(node));
		}
	}

	return false;
}



void TrieAction(){

	ATrie t = init();

	int op;
	char w[20];

	while(in >> op){
		
		in >> w;
	
		switch(op){
			case 0:
				insertKey(t, w);
				break;

			case 1:
				deleteKey(t->root, w, 0);
				break;

			case 2:
				out << countKey(t, w) << "\n";
				break;

			case 3:
				out << countPrefixKey(t, w) << "\n";
				break;
		}
	}
}



int main(){

	TrieAction();

	return 0;
}