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

typedef struct Trie{
    int count, nrfii;
    struct Trie* child[26];
} Trie;

Trie *newNode() {
    Trie *newNode = malloc(sizeof(Trie));
    newNode->count = 0;
    newNode->nrfii = 0;
    for (int i = 0; i < 26; i++)
        newNode->child[i] = NULL;
    return newNode;
}

void init(Trie **root) {
    *root = newNode();
}

void insert(Trie *root, char const *word) {
    int i = -1;
    while (word[++i]) {
        int c = word[i] - 'a';
        if (!root->child[c]) {
            root->child[c] = newNode();
            root->nrfii++;
        }
        root = root->child[c];
    }
    root->count++;
}

void delete(Trie *root, char const *word) {
    if (!word[0])
        return;

    int i = -1;
    while (word[++i + 1]) {
        int c = word[i] - 'a';
        if (!root->child[c])
            return;
        Trie *child = root->child[c];
        if (!child->count && !child->nrfii) {
            free(child);
            root->nrfii--;
            root->child[word[i] - 'a'] = NULL;
            return;
        }
        root = root->child[c];
    }
    Trie *child = root->child[word[i] - 'a'];
    if (child->count)
        child->count--;
    if (!child->count && !child->nrfii) {
        free(child);
        root->nrfii--;
        root->child[word[i] - 'a'] = NULL;
    }
}

Trie *freeTrieUtil(Trie *root) {
    if (!root)
        return NULL;

    for (int i = 0; i < 26; i++) {
        if (root->child[i])
            root->child[i] = freeTrieUtil(root->child[i]);
    }
    free(root);
    return NULL;
}

void freeTrie(Trie **pTrie) {
    Trie *root = *pTrie;
    for (int i = 0; i < 26; i++)
        root->child[i] = freeTrieUtil(root->child[i]);
    free(*pTrie);
}

Trie *search(Trie *root, char const *word) {
    int i = -1;
    while (word[++i]) {
        int c = word[i] - 'a';
        if (!root->child[c])
            return NULL;
        root = root->child[c];
    }
    return root;
}

int commonPrefixLength(Trie *root, const char *word) {
    int i = -1;
    while (word[++i]) {
        int c = word[i] - 'a';
        if (!root->child[c])
            return i;
        root = root->child[c];
    }
    return i;
}

int main() {
    FILE *inputFile = fopen("trie.in", "r");
    FILE *outputFile = fopen("trie.out", "w");
    Trie *root;
    init(&root);
    int command;
    int queryCnt = 0, commandCnt = 0;
    char word[21];
    while (fscanf(inputFile, "%d", &command) != EOF) {
        commandCnt++;
        fscanf(inputFile, "%s", word);
        switch (command) {
            case 0:
                insert(root, word);
                break;
            case 1:
                delete(root, word);
                break;
            case 2: {
                queryCnt++;
                Trie *wordNode = search(root, word);
                if (wordNode)
                    fprintf(outputFile, "%d\n", wordNode->count);
                else
                    fprintf(outputFile, "0\n");
                break;
            }
            case 3:
                queryCnt++;
                fprintf(outputFile, "%d\n", commonPrefixLength(root, word));
                break;
        }
        if (queryCnt == 3249) {
            printf("%d %s %d", command, word, commandCnt);
        }
    }
    freeTrie(&root);
    fclose(inputFile);
    fclose(outputFile);
    return 0;
}