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

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int count;
    int prefix;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->count = 0;
    node->prefix = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

void insert(TrieNode* root, const char* word) {
    TrieNode* current = root;
    while (*word) {
        int index = *word - 'a';
        if (current->children[index] == NULL) {
            current->children[index] = createNode();
        }
        current->children[index]->prefix++;
        current = current->children[index];
        word++;
    }
    current->count++;
}

void removeWord(TrieNode* root, const char* word) {
    TrieNode* current = root;
    while (*word) {
        int index = *word - 'a';
        current->children[index]->prefix--;
        current = current->children[index];
        word++;
    }
    current->count--;
}

int search(TrieNode* root, const char* word) {
    TrieNode* current = root;
    while (*word) {
        int index = *word - 'a';
        if (current->children[index] == NULL) {
            return 0;
        }
        current = current->children[index];
        word++;
    }
    return current->count;
}

int findLongestPrefix(TrieNode* root, const char* word) {
    TrieNode* current = root;
    int length = 0;
    int maxPrefix = 0;
    while (*word) {
        int index = *word - 'a';
        if (current->children[index] == NULL) {
            return maxPrefix;
        }
        current = current->children[index];
        length++;
        if (current->prefix == 1) {
            maxPrefix = length;
        }
        word++;
    }
    return maxPrefix;
}

int main() {
    TrieNode* root = createNode();

    int operation;
    char word[21];

    FILE* inputFile = fopen("trie.in", "r");
    FILE* outputFile = fopen("trie.out", "w");

    while (fscanf(inputFile, "%d %s", &operation, word) == 2) {
        switch (operation) {
            case 0:
                insert(root, word);
                break;
            case 1:
                removeWord(root, word);
                break;
            case 2:
                fprintf(outputFile, "%d\n", search(root, word));
                break;
            case 3:
                fprintf(outputFile, "%d\n", findLongestPrefix(root, word));
                break;
            default:
                break;
        }
    }

    fclose(inputFile);
    fclose(outputFile);

    return 0;
}