#include <fstream>
#include <iostream>

class Trie{
private:
    struct Node{
        Node* child[26];
        unsigned int wordEnd = 0;

        Node(){
            for(unsigned short i = 0; i < 26; i++) child[i] = nullptr;
        }
    };



public:
    Node* root = new Node();

    void insert(const char* str, Node* node){
        if(*str == '\0'){
            node->wordEnd++;
            return;
        }

        if(node->child[*str - 'a'] == nullptr){
            node->child[*str - 'a'] = new Node();
        }

        insert(str + 1, node->child[*str - 'a']);
    }

    Node* remove(const char* str, Node* node){
        if(*str == '\0'){
            node->wordEnd--;
        }
        else node->child[*str - 'a'] = remove(str + 1, node->child[*str - 'a']);

        if(node->wordEnd == 0){
            bool empty = true;

            for(unsigned short i=0; i < 26; i++){
                if(node->child[i] != nullptr){
                    empty = false;
                }
            }

            if(empty == true){
                return nullptr;
            }
        }

        return node;
    }

    unsigned int search(const char* str, Node* node){
        if(*str == '\0'){
            return node->wordEnd;
        }

        if(node->child[*str - 'a'] != nullptr){
            return search(str + 1, node->child[*str - 'a']);
        }

        return 0;
    }

    unsigned int prefix_search(const char* str, Node* node, unsigned int length = 0){
        if(*str == '\0' || node->child[*str - 'a'] == nullptr){
            return length;
        }

        return prefix_search(str + 1, node->child[*str - 'a'], length + 1);
    }



};

int main()
{
    Trie trie;

    std::ifstream fin("trie.in");
    std::ofstream fout("trie.out");

    unsigned short op;
    char* word = new char;

    while(fin>>op>>word){
        if(op == 0) trie.insert(word, trie.root);
        else if(op == 1) trie.remove(word, trie.root);
        else if(op == 2) fout<<trie.search(word, trie.root)<<'\n';
        else fout<<trie.prefix_search(word, trie.root)<<'\n';
    }
}