#include <stdio.h>
#include <stack>
#include <strings.h>

using namespace std;

const int LINE_SIZE = 32;

class Trie {
private:
    static const int ALPHABET_SIZE = 26;

    class TrieNode {
    public:
        int no_sons;
        int word_freq;
        TrieNode * sons[ALPHABET_SIZE];
        TrieNode() {
            no_sons = 0;
            word_freq = 0;
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                sons[i] = NULL;
            }
        }
    };

    TrieNode * root;
    void free_resources(TrieNode * node);
    bool delete_word_helper(TrieNode * node, char * word);

public:
    Trie();
    ~Trie();
    void add_word(char * word);
    void delete_word(char * word);
    int get_word_freq(char * word);
    int longest_existing_prefix(char * word);
};

Trie::Trie() {
    root = new TrieNode();
}

Trie::~Trie() {
    free_resources(root);
}

void Trie::free_resources(TrieNode * node) {
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->sons[i] != NULL) {
            free_resources(node->sons[i]);
        }
    }
    delete node;
}

void Trie::add_word(char * word) {
    int word_pos = 0;
    TrieNode * node = root;

    while (word[word_pos] != '\0') {
        int son_index = word[word_pos] - 'a';
        if (node->sons[son_index] == NULL) {
            node->sons[son_index] = new TrieNode();
            node->no_sons++;
        }
        node = node->sons[son_index];
        word_pos++;
    }

    node->word_freq++;
}

void Trie::delete_word(char * word) {
    delete_word_helper(root, word);
}

bool Trie::delete_word_helper(TrieNode * node, char * word) {
    // nothing to delete
    if (node == NULL || (*word == '\0' && node->word_freq == 0)) {
        return false;
    }

    if (*word == '\0') {
        node->word_freq--;
    } else if (delete_word_helper(node->sons[*word - 'a'], word + 1)) {
        node->sons[*word - 'a'] = NULL;
        node->no_sons--;
    }

    if (node->word_freq == 0 && node->no_sons == 0 && node != root) {
        delete node;
        return true;
    }

    return false;
}

int Trie::get_word_freq(char * word) {
    int word_pos = 0;
    TrieNode * node = root;

    while (node != NULL && word[word_pos] != '\0') {
        node = node->sons[word[word_pos] - 'a'];
        word_pos++;
    }

    return node != NULL ? node->word_freq : 0;
}

int Trie::longest_existing_prefix(char * word) {
    int word_pos = 0;
    TrieNode * node = root;

    while (node != NULL && word[word_pos] != '\0') {
        node = node->sons[word[word_pos] - 'a'];
        word_pos++;
    }

    if (node == NULL) {
        word_pos--;
    }
    return word_pos;
}

int main() {
    FILE * fin, * fout;
    char line[LINE_SIZE];
    int ans;

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

    Trie trie;
    while (fgets(line, LINE_SIZE, fin) != NULL) {
        line[strlen(line) - 1] = '\0';
        if (line[0] == '0') {
            trie.add_word(line + 2);
        } else if (line[0] == '1') {
            trie.delete_word(line + 2);
        } else if (line[0] == '2') {
            ans = trie.get_word_freq(line + 2);
            fprintf(fout, "%d\n", ans);
        } else if (line[0] == '3') {
            ans = trie.longest_existing_prefix(line + 2);
            fprintf(fout, "%d\n", ans);
        }
    }

    fclose(fin);
    fclose(fout);

    return 0;
}