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



struct TrieNode {
	struct TrieNode *child[26];
	int childrenCount; // how many children it has - presumably useful for deletion
	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[150000]; // chunk of 120000 nodes
int alloc_cnt;
TrieNode T;

/* 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 */

void add(TrieNode *node, char *s) {  // assume word '\0' terminated
	if (s[0] < 'a') { // have hit either '\0' or '\n'
		node->freq++;
		return;
	}
	if (node->child[CH] == NULL) {
		//node->child[CH] = calloc(1, sizeof(struct TrieNode));
		node->child[CH] = &mem[alloc_cnt++];
		node->childrenCount++;
	}
	add(node->child[CH], s+1);
}

int rm(TrieNode *node, char *s) {
	if  (s[0] < 'a') {
        node->freq--;
	}
	else if (rm(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;
	/*if  (s[0] < 'a') {
        node->freq--;
        return;
	}
	rm(node->child[CH], s+1);*/
}

int query(TrieNode *node, char *s) {
	if (*s < 'a')
		return node->freq;

	if (node->child[CH])
		return query(node->child[CH], s+1);
	return 0;
}

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

int main() {
	char line[ 32 ];
 
    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 ) ) {
		switch( line[0] ) {
			case '0': add( &T, line+2 ); break;
			case '1': rm( &T, line+2 ); break;
			case '2': printf( "%d\n", query( &T, line+2 ) ); break;
			case '3': printf( "%d\n", prefix( &T, line+2, 0 ) ); break;
		}
		fgets( line, 32, stdin );
	}
	printf("alloc_cnt = %d\n", alloc_cnt);
	return 0;
}