#include <stdio.h>
#include <stdlib.h>
 
#define CH (*s - 'a')

struct TrieNode {
	struct TrieNode *parent;
	struct TrieNode *child[26];
	char childrenCount; // how many children it has - presumably useful for deletion
	short int freq; // nr of appearances of the word formed by the characters belonging to the path starting at root and ending here
};
typedef struct TrieNode TrieNode;

TrieNode mem[115000]; // chunk of 120000 nodes
int alloc_cnt = 1;
TrieNode *T = mem;  // first node in chunk we'll be using as root
int dbg_flag;

/* 0 w - adauga o aparitie a cuvantului w in lista
1 w - sterge o aparitie a cuvantului w din lista
2 w - tipareste numarul de aparitii ale cuvantului w in lista
3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista

Pentru toate operatiile, cuvantul w este format din maxim 20 de caractere din intervalul 'a'..'z'
Numarul total de operatii nu va depasi 100 000
Operatiile de tip 1 w vor aparea numai daca w apare cel putin o data in lista de cuvinte */

/*
int rm_rec(TrieNode *node, char *s) {
	if  (s[0] < 'a') {
        node->freq--;
	}
	else if (rm_rec(node->child[CH], s+1)) {
		node->child[CH] = 0;
		node->childrenCount--;
	}
	if (node->freq == 0 && node->childrenCount == 0 && node != T) {
		//free(node);
		return 1;
	}
	return 0;
}
*/

void add(TrieNode *node, char *s) {  // assume word '\0' terminated
    char ch;
	while (1) {
		ch = *s - 'a';
		if (ch < 0) { // have hit either '\0' or '\n'
			node->freq++;
		    return;
		}
		if (node->child[ch] == NULL) {
		    node->child[ch] = mem + alloc_cnt++;
		    node->child[ch]->parent = node;
		    node->childrenCount++;
	    }
		node = node->child[ch];
		s++;
	}
}
 
int rm(TrieNode *node, char *s) {
	char ch, *f;
	while (1) {
		ch = *s - 'a';
		if (ch < 0) { // have hit either '\0' or '\n'
		    node = ((--node->freq == 0 && node->childrenCount == 0) ? node->parent : NULL);
		    break;
		}
		node = node->child[ch];
		s++;
	}
	f = s-1;
	while (node != NULL) {
		ch = *f - 'a';
		node->child[ch] = 0;
		node->childrenCount--;
		node = ((node->freq == 0 && node->childrenCount == 0) ? node->parent : NULL);
		f--;
	}
}



/*
void rm(TrieNode *node, char *s) {
	char ch;

	for (;;) {
		ch = *s - 'a';
		if (ch < 0) { // have hit either '\0' or '\n'
		    node->freq--;
		    node = ((node->freq == 0 && node->childrenCount == 0) ? node->parent : NULL);
		    if (node == NULL) // no need to fix up the parent chain
	            return;
		    s--;
		    break;
		}
		node = node->child[ch];
		s++;
	}
	for (;;) {
		node->child[CH] = NULL;
		node->childrenCount--;
		node = ((node->freq == 0 && node->childrenCount == 0) ? node->parent : NULL);
		if (node == NULL)
		    return;
		s--;
	}
}*/

int query(TrieNode *node, char *s) {
	char ch;
	while (1) {
		ch = *s - 'a';
		if (ch < 0)
		    return node->freq;
		node = node->child[ch];
	    if (node == NULL)
	        return 0;
	    s++;
	}
	return 0;
}

int prefix(TrieNode *node, char *s) {	
    short int t = 0;
    char ch;
    
	while (1) {
		ch = *s - 'a';
		node = node->child[ch];
		if (!node || ch < 0)
		    return t;
		s++;
		t++;
	}
}

void inorder(TrieNode *node, char *buf, int k) {
	int i;
	
	if (node->freq > 0) {
		buf[k] = '\0';
		printf("%s\n", buf);
	}
	for (i = 0; i < 26; i++)
	    if (node->child[i]) {
	    	buf[k] = i+'a';
	    	inorder(node->child[i], buf, k+1);
		}
}

int main() {
	char line[32], buf[32];
	char *s;
 
    freopen( "trie.in", "r", stdin );
	freopen( "trie.out", "w", stdout );
	//freopen( "grader_test20.in", "r", stdin );
	//freopen( "grader_test20.out", "w", stdout );
	fgets(line, 32, stdin);
 
	while(!feof(stdin)) {
		s = line+2;
		//if (strstr(s, "viermusor\n"))
		//    break;
		switch(line[0]) {
			case '0': add(T, s); 
			    break;
			case '1': rm(T, s); 
			    break;
			case '2': printf( "%d\n", query(T, s)); 
			    break;
			case '3': printf( "%d\n", prefix(T, s)); 
			    break;
		}
		fgets(line, 32, stdin);
	}
	//inorder(T, buf, 0);
	//printf("alloc_cnt = %d\n", alloc_cnt);
	return 0;
}