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

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

Trie *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);
}

int removeWord(Trie *where, char *w) {
	if (!*w)
		--where->count;
	else if (removeWord(where->next[normChar(*w)], w+1)) {
		where->next[normChar(*w)] = 0;
		--where->childs;
	}

	if (!where->count && !where->childs && (where != trie)) {
		free(where);
		return 1;
	}
	return 0;
}

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)]; ++w) {
		++len;
		where = where->next[normChar(*w)];
	}
	
	return len;
}

void printPath(Trie *where, char *w) {
	for (; *w && where; ++w) {
		printf("(%d %d) -%c-> ", where->count, where->childs, *w);
	}
	printf("(%d %d)\n", where->count, where->childs);
}

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

	trie = mkTrie();

	FILE *fi = fopen("grader_test2.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:
//				printf(">>> ");
//				printPath(trie, w);
				fprintf(fo, "%d\n", longestPrefix(trie, w));
				break;
		}
	}
	fclose(fo);
	fclose(fi);

	return 0;
}