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

FILE *in, *out;

typedef struct
{
    int nrcopii, nrsuf;
    struct Trie *next[26];
} Trie;

void printgay(Trie *nod, int depth)
{
    int i;
    printf("%d %d %d:", depth, nod->nrsuf, nod->nrcopii);
    for(i = 0; i < 26; i++) {
            if(nod->next[i] != 0) {
                printf("%c ", 'a' + i);
            }
    }
    printf("\n");

    for(i = 0; i < 26; i++) {
            if(nod->next[i] != 0) {
                printgay(nod->next[i], depth + 1);
            }
    }
}


void cuvnou(Trie *nod, char *x)
{
    Trie *nou;
    if(x[0] >= 'a' && x[0] <= 'z') {
        if(nod->next[x[0] - 'a'] == 0) {
                nou = calloc(1, sizeof(Trie));
                nod->next[x[0] - 'a'] = nou;
                nod->nrcopii++;
                cuvnou(nou, x + 1);
        } else {
                nou = nod->next[x[0] - 'a'];
                cuvnou(nou, x + 1);
        }
    } else {
        nod->nrsuf++;
        return;
    }
}

void prefcom(Trie *nod, char *x)
{
    int i;
    i = 0;
    while(nod->next[x[i] - 'a'] != 0) {
        nod = nod->next[x[i] - 'a'];
        i++;
    }
    fprintf(out, "%d\n", i);

    return;
}

void nraparitii(Trie *nod, char *x)
{
    int i, nrap;
    i = 0;
    nrap = 0;
    while((nod->next[x[i] - 'a'] != 0)) {
        if(x[i + 1] == 0) {
            nod = (nod->next[x[i] - 'a']);
            nrap = nod->nrsuf;
        } else {
            nod = nod->next[x[i] - 'a'];
            i++;
        }
    }
    fprintf(out, "%d\n", nrap);
    return;
}

int deletecuv(Trie *nod, char *x)
{
    int y;
    Trie *aux;
    if(x[1] == 0) {
            aux = nod->next[x[0] - 'a'];
            if(aux->nrcopii > 0) {
                aux->nrsuf--;
                return 3;
            } else {
                if(aux->nrsuf == 1) {
                        free(aux);
                        nod->next[x[0] - 'a'] = 0;
                        nod->nrcopii--;
                        if(nod->nrcopii == 0) {
                                return 1;
                        } else {
                                return 3;
                        }
                        //return 1;
                } else {
                    aux->nrsuf--;
                    return 3;
                }
            }
    }
    y = deletecuv(nod->next[x[0] - 'a'], x + 1);
    if(y == 3) {
            return 3;
    }
    if(y == 0) {
            free(nod->next[x[0] - 'a']);
            nod->next[x[0] - 'a'] = 0;
            nod->nrcopii--;
            if(nod->nrcopii == 0) {
                    if(nod->nrsuf == 0) {
                        return 0;
                    } else {
                        return 3;
                    }
            } else {
                    return 3;
            }
    }
}

int main () {

    char gay[21], caz;
    Trie *first;

    in = fopen("trie.in", "r");
    out = fopen("trie.out", "w");

    caz = fgetc(in);

    first = (Trie*)calloc(1, sizeof(Trie));

    while(caz != EOF) {
        fgetc(in);
        fscanf(in, "%s", gay);
        fgetc(in);
        switch(caz) {
            case '0':
                cuvnou(first, gay);
                break;
            case '1':
                deletecuv(first, gay);
                break;
            case '2':
                nraparitii(first, gay);
                break;
            case '3':
                prefcom(first, gay);
                break;
        }
        caz = fgetc(in);
    }
    //printgay(first, 0);

    fclose(in);
    fclose(out);

    return 0;
}