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

struct node{
    int occurences;
    struct node *edge[26];
};
struct node *head = NULL;

void Initialize(){
    head = (struct node*)malloc(sizeof(struct node));
    head -> occurences = 0; int i;

    for(i=0; i<26; i++){
        head -> edge[i] = NULL;
    }
}
void Insert(char word[]){
    struct node *ptr = head;
    int i, j, len = strlen(word), index;

    for(i=0; i<len; i++, ptr = ptr -> edge[index]){
        index = tolower(word[i]) - 'a';

        if(ptr -> edge[index] == NULL){
            ptr -> edge[index] = (struct node*)malloc(sizeof(struct node));
            (ptr -> edge[index]) -> occurences = 0;

            for(j=0; j<26; j++){
                (ptr -> edge[index]) -> edge[j] = NULL;
            }
        }
    }ptr -> occurences++;
}
int Search(char word[]){
    struct node *ptr = head;
    int i, len = strlen(word), index;

    for(i=0; i<len; i++, ptr = ptr -> edge[index]){
        index = tolower(word[i]) - 'a';
        if(ptr -> edge[index] == NULL) return 0;
    }
    return ptr -> occurences;
}
int LongestPrefix(char word[]){
    struct node *ptr = head;
    int i, j, index, prefix = 0, len = strlen(word);

    for(i=0; i<len; i++, ptr = ptr -> edge[index]){
        index = tolower(word[i] - 'a');
        if(ptr -> edge[index] == NULL) return prefix;
        int verges = 0;

        for(j=0; j<26; j++){
            verges += !!((ptr -> edge[index]) -> edge[j]);
        }
        if(verges){
            prefix = i+1;
        }
    }
    return prefix;
}
void Delete(char word[21]){
    struct node *ptr = head, *depth = NULL;
    int i, j=-1, k, index, len = strlen(word), verges = 0;

    for(i=0; i<len; i++, ptr = ptr -> edge[index]){
        index = tolower(word[i] - 'a');
        if(ptr -> edge[index] == NULL) return;
        if(i != len-1 && ptr -> occurences){
            depth = ptr;
            j = i;
        }
        verges = 0;

        for(k = 0; i && k < 26; k++){
            verges += !!(ptr -> edge[k]);
        }if(verges > 1 && i > j){
            j = i;
            depth = ptr;
        }

    }if(ptr -> occurences == 0) return;

    verges = 0;

    for(i=0; i<26; i++){
        verges += !!(ptr -> edge[i]);
    }
    if(ptr -> occurences > 1 || ((ptr -> occurences == 1) && verges)){
        ptr -> occurences--;
        return;
    }
    if(depth == NULL){
        index = tolower(word[0] - 'a');
        ptr = head -> edge[index];
        head -> edge[index] = NULL;

        for(i=1; i<len; i++){
            index = tolower(word[i] - 'a');
            struct node *temp = ptr;
            ptr = ptr -> edge[index];
            free(temp);
        }free(ptr);
    }else{
        k = len - j;
        index = tolower(word[j] - 'a');
        struct node *temp = depth;
        depth = depth -> edge[index];
        temp -> edge[index] = NULL;

        for(i=1; i<k; i++){
            index = tolower(word[j+i] - 'a');
            temp = depth;
            depth = depth -> edge[index];
            free(temp);
        }free(depth);
    }
}

int main(){

Initialize();

freopen("trie.in", "r", stdin);
freopen("trie.out", "w", stdout);

int task;
char word[21], ch=0;

while(1){
    if(isdigit(ch)){
        task = ch - 48;
    }else{
        scanf("%d", &task);
    }
    scanf("%s", word);

    if(task==0){
        Insert(word);
    }
    if(task==1){
        Delete(word);
    }
    if(task==2){
        printf("%d\n", Search(word));
    }
    if(task==3){
        printf("%d\n", LongestPrefix(word));
    }
    while(1){
        ch = getchar();
        if(isdigit(ch) || ch==EOF){
            break;
        }
    }
    if(ch==EOF) break;
}

return 0;
}

/*
Insert("ma");
Insert("mic");
Insert("mari");
Insert("mare");
Insert("mare");
Insert("lac");
Insert("lat");
Insert("lung");

printf("ma %d\n", Search("ma"));
printf("mic %d\n", Search("mic"));
printf("mari %d\n", Search("mari"));
printf("mare %d\n", Search("mare"));
printf("lac %d\n", Search("lac"));
printf("lat %d\n", Search("lat"));
printf("lung %d\n", Search("lung"));
*/

/*
freopen("trie.in", "r", stdin);
freopen("trie.out", "w", stdout);

int task;
char word[21], ch=0;

while(1){
    if(isdigit(ch)){
        task = ch - 48;
    }else{
        scanf("%d", &task);
    }
    scanf("%s", word);

    if(task==0){
        Insert(word);
    }
    if(task==1){
        Delete(word);
    }
    if(task==2){
        printf("%s %d\n", word, Search(word));
    }
    if(task==3){
        printf("%s %d\n", word, LongestPrefix(word));
    }
    while(1){
        ch = getchar();
        if(isdigit(ch) || ch==EOF){
            break;
        }
    }
    if(ch==EOF) break;
}
*/