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

struct node {
    char value;
    int ends;
    int children_no;
    node* children[30];
};

node *create_node(char c)
{
    node *n = (node*)calloc(1, sizeof(node));
    n->value = c;

    return n;
}

void add_word(node *t, char *word, int index)
{
    int c_index = word[index] - 'a';

    if (t->children[c_index] == NULL) {
        t->children[c_index] = create_node(word[index]);
        t->children_no++;
    }

    if (index == (strlen(word) - 1))
        t->children[c_index]->ends++;
    else
        add_word(t->children[c_index], word, index + 1);
}

void delete_word(node *t, char *word, int index)
{
    int c_index = word[index] - 'a';

    if (t->children[c_index] == NULL)
        return;

    if (index == (strlen(word) - 1)) 
        t->children[c_index]->ends--;    
    else 
        delete_word(t->children[c_index], word, index + 1);

    if (t->children[c_index]->ends == 0 && t->children[c_index]->children_no == 0) {
        free(t->children[c_index]);
        t->children[c_index] = NULL;
        t->children_no--;
    }
}

int count_words(node *t, char *word, int index)
{
    int c_index = word[index] - 'a';

    if (t->children[c_index] == NULL)
        return 0;

    if (index == (strlen(word) - 1)) 
        return t->children[c_index]->ends;
    else
        return count_words(t->children[c_index], word, index + 1);
}

int prefix(node *t, char *word, int index)
{
    int c_index = word[index] - 'a';

    if (t->children[c_index] == NULL)
        return 0;

    if (index == (strlen(word) - 1))
        return strlen(word);

    int p = prefix(t->children[c_index], word, index + 1);
    if (p == 0)
        return (index + 1);
    return p;
}

int main()
{
    node *t = create_node(' ');

    FILE *fin = fopen("trie.in", "r");
    FILE *fout = fopen("trie.out", "w");

    while (!feof(fin)) {
        int code;
        char word[100] = {0};

        fscanf(fin, "%d %s\n", &code, word);

        switch (code) {
            case 0:
                add_word(t, word, 0);
                break;
            case 1:
                delete_word(t, word, 0);
                break;
            case 2:
                fprintf(fout, "%d\n", count_words(t, word, 0));
                break;
            case 3:
                fprintf(fout, "%d\n", prefix(t, word, 0));
                break;
        }
    }

    fclose(fin);
    fclose(fout);

    return 0;
}