#include <stdio.h>
#include <vector>
#include <algorithm>
#define MAXOI 1025
#define MAXH 10007

class Node {
	int count;
	Node *neigh[30];
	public:
		int brcount;
		Node();
		void add_neigh(const char where);
		void del_neigh(const char where);
		Node *get_neigh(const char where);
		int get_count();
		void set_count(int value);
};

class Trie {
	Node root;
	private:
		void del_word_aux(const char *word, int poz, Node &current);	
	public:
		Trie();
		void add_word(const char *word);
		void del_word(const char *word);
		int numWord(const char *word);
		int numWordPref(const char *word);

};

Node::Node() {
	count = 0;
	for (int i = 0; i < 30; i++) {
		neigh[i] = NULL;
	}
//	fprintf(stderr, "Finished constructing node\n");
}

Node* Node::get_neigh(const char where) {
	return neigh[where - 'a'];
}

void Node::add_neigh(const char where) {
//	fprintf(stderr, "Adding neighbour in Node, %d %p\n", where - 'a', neigh[where - 'a']);
	if (neigh[where - 'a'] == NULL) {
//		fprintf(stderr, "Saw that it is null\n");
		neigh[where - 'a'] = new Node();
	}
	brcount++;
}

void Node::del_neigh(const char where) {
	neigh[where - 'a'] = NULL;
}

int Node::get_count() {
	return count;
}

void Node::set_count(int value) {
	count = value;
}

void Trie::add_word(const char *word) {
	Node *curNode = &(this->root);
	for (int poz = 0; word[poz] != '\0'; poz++){
//		fprintf(stderr, "Adding at poz: %d %s %p\n", poz, word, curNode);
		curNode->add_neigh(word[poz]);
//		fprintf(stderr, "Adding complete\n");
/*		for (int i = 0; i < 30; i++) {
			fprintf(stderr, "%p ", curNode->get_neigh((char) ('a' + i)));
		}*/
		//fprintf(stderr, "\n");
		curNode = curNode->get_neigh(word[poz]);
	}
	curNode->set_count(curNode->get_count() + 1);
}

void Trie::del_word(const char *word) {
	//fprintf(stderr, "Deleting %s\n", word);
	del_word_aux(word, 0, root);
}

void Trie::del_word_aux(const char *word, int poz, Node &current) {
	if (word[poz] == '\0') return;
	//fprintf(stderr, "Deleting from word %s %c %d\n", word, word[poz], current.get_neigh(word[poz])->brcount);
	current.get_neigh(word[poz])->brcount--;
	del_word_aux(word, poz + 1, *(current.get_neigh(word[poz])));
	if (current.get_neigh(word[poz])->brcount == 0) {
		current.del_neigh(word[poz]);
	}
}


Trie::Trie() {
	this->root = Node();
}
int Trie::numWord(const char *word) {
	Node *curNode = &(this->root);
	for (int poz = 0; word[poz] != '\0'; poz++){
		curNode = curNode->get_neigh(word[poz]);
		//fprintf(stderr, "Going for letter %c\n", word[poz]);
		if (curNode == NULL) return 0;
	}
	return curNode->get_count();
}

int Trie::numWordPref(const char *word) {
	int poz;
	Node *curNode = &(this->root);
	for (poz = 0; word[poz] != '\0'; poz++){
		curNode = curNode->get_neigh(word[poz]);
		//fprintf(stderr, "Going for letter %c\n", word[poz]);
		if (curNode == NULL) {
			//fprintf(stderr, "Bad letter\n");
			return poz;
		}
	}
	return poz;
}


int main() {

	FILE *f = fopen("trie.in", "r");
	FILE *g = fopen("trie.out", "w");

	Trie t = Trie();
	int op;
	char word[30];

	while (fscanf(f, "%d %s", &op, word) > 0) {
		if (op == 0) {
			//fprintf(stderr, "Insertion %d %s\n", op, word);
			t.add_word(word);
			//fprintf(stderr, "Done Insertion\n");
		}
		if (op == 1) {
			t.del_word(word);
		}
		if (op == 2) {
			fprintf(g, "%d\n", t.numWord(word));
		}
		if (op == 3) {
			fprintf(g, "%d\n", t.numWordPref(word));
		}
	}

	fclose(f);
	fclose(g);
}