#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef struct node {
int apparitions;
int totalApparitions;
struct node *children['z' - 'a' + 2];
} NODE;
NODE *root;
NODE *addApparition(NODE *p, char *s){
if (p == NULL) {
p = (NODE *)malloc(sizeof(NODE));
p->apparitions = 0;
p->totalApparitions = 0;
for (int i=0; i< ('z'-'a'+1); i++){
p->children[i] = NULL;
}
}
p->totalApparitions++;
//if this is the last character
if (s[0] == '\0') {
p->apparitions++;
} else {
p->children[s[0]-'a'] = addApparition( p->children[s[0]-'a'], s+1);
}
return p;
}
NODE *removeApparition(NODE *p, char *s){
p->totalApparitions--;
//if this is the last character
if (s[0] == '\0') {
p->apparitions--;
} else {
p->children[s[0]-'a'] = removeApparition( p->children[s[0]-'a'], s+1);
}
if (p->totalApparitions == 0){
free(p);
return NULL;
}
else {
return p;
}
}
int getNrOfApparitions(NODE *p, char *s){
if (p == NULL){
return 0;
} else {
if (s[0] == '\0') {
return p->apparitions;
} else {
return getNrOfApparitions(p->children[s[0]-'a'], s+1);
}
}
}
int getLongestPrefix(NODE *p, char *s, int currentIndex){
if (p == NULL){
return 0;
}
if (s[0] == '\0') {
if (p->apparitions != 0 || p->totalApparitions != 0){
return currentIndex;
} else {
return 0;
}
}
else {
int index = getLongestPrefix(p->children[s[0]-'a'], s+1, currentIndex+1);
if (index != 0){
return index;
} else {
if ((p->children[s[0]-'a'] == NULL && p->totalApparitions>0) || p->totalApparitions - p->children[s[0]-'a']->totalApparitions != 0){
return currentIndex;
} else {
return 0;
}
}
}
}
void handleInput(int op, char *s){
int nrOfApparitions, longestPrefix;
switch(op){
case 0:
root = addApparition(root, s);
break;
case 1:
root = removeApparition(root, s);
break;
case 2:
nrOfApparitions = getNrOfApparitions(root, s);
printf("%d\n", nrOfApparitions);
break;
case 3:
longestPrefix = getLongestPrefix(root, s, 0);
printf("%d\n", longestPrefix);
break;
}
}
int main()
{
freopen("trie.in", "r", stdin);
freopen("trie.out", "w", stdout);
int op;
char s[21];
while (scanf("%d ", &op) != EOF){
char c;
scanf("%c", &c);
int index = 0;
while (c <= 'z' && c >= 'a'){
s[index++] = c;
scanf("%c", &c);
}
s[index] = '\0';
handleInput(op, s);
}
return 0;
}