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

#define MAX_CHILD

typedef struct Trie Node;

struct Trie {
	int count;
	int numChild;
	struct Trie* child[MAX_CHILD];
};

Node *trie;

Node* getNode()
{
	Node *node = malloc(sizeof(Node));
	node->count = 0;
	node->numChild = 0;
	int i;

	for (i = 0; i < MAX_CHILD; i++)
		node->child[i] = NULL;
	return node;
}


void insert(Node *node, char *w)
{
	if (*w == '\n') {
		node->count++;
		return;
	}

	if (node->child[*w - 'a'] == NULL) {
		node->child[*w - 'a'] = getNode();
		node->numChild++;
	}
	insert(node->child[*w - 'a'], w + 1);
}


int delete(Node *node, char *w)
{
	if (*w == '\n')
		node->count--;
	else if (delete(node->child[*w - 'a'], w + 1)) {
		node->child[*w - 'a'] = NULL;
		node->numChild--;
	}
	if (node->count == 0 && node->numChild == 0 && node != trie) {
		free(node);
		return 1;
	}
	return 0;
}

int print(Node *node, char *w)
{
	if (*w == '\n')
		return node->count;
	if (node->child[*w - 'a'])
		return print(node->child[*w - 'a'], w + 1);
	return 0;
}

int pref(Node *node, char *w, int cnt)
{
	if (*w == '\n' || node->child[*w - 'a'] == NULL)
		return cnt;
	return pref(node->child[*w - 'a'], w + 1, cnt + 1);
}

int main(void)
{
	FILE *f = fopen("trie.in", "rt");
	FILE *g = fopen("trie.out", "wt");
	char w[256];
	int op;
	trie = getNode();

	while (fgets(w, 256, f)) {
		sscanf(w, "%d", &op);

		switch(op) {
		case 0:
			insert(trie, w + 2);
			break;
		case 1:
			delete(trie, w + 2);
			break;
		case 2:
			fprintf(g, "%d\n", print(trie, w + 2));
			break;
		case 3:
			fprintf(g, "%d\n", pref(trie, w + 2, 0));
			break;
		}
	}
	fclose(f);
	fclose(g);
	free(trie);
	return 0;
}