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

typedef struct Trie {
	struct Trie *next[26];
	int count, childs;
} Trie;

Trie* mkTrie() {
	Trie *t = malloc(sizeof(Trie));
	memset(t->next, 0, sizeof(t->next));
	t->count = t->childs = 0;
	return t;
}

int normChar(char c) {
	return c - 'a';
}

void insertWord(Trie *where, char *w) {
	for (; *w; ++w) {
		++where->childs;
//		printf("(%d %d) -%c-> ", where->count, where->childs, *w);
		if (where->next[normChar(*w)])
			where = where->next[normChar(*w)];
		else
			where = where->next[normChar(*w)] = mkTrie();
	}

	++where->count;

//	printf("(%d %d)\n", where->count, where->childs);
}

void removeWord(Trie *where, char *w) {
	for (; *w; ++w) {
		--where->childs;
//		printf("(%d %d) -%c-> ", where->count, where->childs, *w);
		where = where->next[normChar(*w)];
	}

	--where->count;
//	printf("(%d %d)\n", where->count, where->childs);
}

int countOccs(Trie *where, char *w) {
	for (; *w; ++w) {
		if (where->next[normChar(*w)])
			where = where->next[normChar(*w)];
		else
			return 0;
	}

	return where->count;
}

int longestPrefix(Trie *where, char *w) {
	int len = 0;

	for (; *w && where->next[normChar(*w)] && where->next[normChar(*w)]->childs; ++w) {
		++len;
		if (where->next[normChar(*w)])
			where = where->next[normChar(*w)];
		else
			break;
	}

	return len;
}

int main(int argc, char *argv[]) {
	int op;
	char w[32];

	Trie *trie = mkTrie();

	FILE *fi = fopen("trie.in", "r");
	FILE *fo = fopen("trie.out", "w");
	while (fscanf(fi, "%d %s", &op, w) != EOF) {
		switch (op) {
			case 0: 
				insertWord(trie, w);
				break;
			case 1:
				removeWord(trie, w);
				break;
			case 2:
				fprintf(fo, "%d\n", countOccs(trie, w));
				break;
			case 3:
				fprintf(fo, "%d\n", longestPrefix(trie, w));
				break;
		}
	}
	fclose(fo);
	fclose(fi);

	return 0;
}