/*
 * =====================================================================================
 *
 *       Filename:  trie.cpp
 *
 *    Description: http://www.infoarena.ro/problema/trie 
 *                 http://www.infoarena.ro/job_detail/1449427?action=view-source  
 *
 *        Version:  1.0
 *        Created:  06/09/2015 02:19:02 PM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */
   
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
    
using namespace std;
    
const int alphabet_size = 26;
    
struct TrieNode {
    int count_childs, count_words;
    vector<TrieNode*> child;
    
    TrieNode() {
        count_childs = count_words = 0;
        child.resize(alphabet_size, NULL);
    }
};
    
TrieNode* root;
    
void pushToTrie(TrieNode* node, int letter, string& str) {
    if (letter == str.size()) { // finished the current word
        node->count_words++;
        return;
    }
    if (node->child[str[letter] - 'a'] == NULL) { // if there isn't a child with that character
        node->child[str[letter] - 'a'] = new TrieNode; // create the child with that character
        node->count_childs++;
    }
    
    pushToTrie(node->child[str[letter] - 'a'], letter + 1, str); // continue with the next character from word
}
  
bool popFromTrie(TrieNode* node, int letter, string& str) {
    if (letter == str.size()) {  // finished the current word
        node->count_words--;
    } else {
        if (popFromTrie(node->child[str[letter] - 'a'], letter + 1, str) == true) { // if I eliminated the child
            node->count_childs--;
            node->child[str[letter] - 'a'] = NULL; // erase the child
        }
    }
    
    if (node->count_childs == 0 &&
        node->count_words == 0 &&
        node != root) { // if the node doesn't have any childs and
                        // doesn't have words that terminate in him and
                        // is not the trie root
        delete node; // erase the node
        return true;
    }
    
    return false;
}
  
int getNumberOfWords(TrieNode* node, int letter, string& str) {
    if (letter == str.size()) // we have reached the end of the word
        return node->count_words; // return the number of words that terminates in this node
  
    if (node->child[str[letter] - 'a'] == NULL) // if there isn't a child with the current letter
        return 0; // we can't go further for searching the words' next character
  
    return getNumberOfWords(node->child[str[letter] - 'a'],
                            letter + 1,  // continue with the next letter 
                            str); 
}
    
int getLengthOfPrefix(TrieNode* node, int letter, string& str) {
    if (letter == str.size() || node->child[str[letter] - 'a'] == NULL) // if I've finished the current word or
                                                                        // there isn't a child with words' current character
        return letter; // return the length found until now
    
    return getLengthOfPrefix(node->child[str[letter] - 'a'], letter + 1, str); // otherwise go to the child with the next character
}
    
int main() {
    int operation;
    string str;
    ifstream input("trie.in");
    ofstream output("trie.out");
    
    root = new TrieNode;
    
    while (input >> operation >> str) {
        if (operation == 0)
            pushToTrie(root, 0, str);
        if (operation == 1)
            popFromTrie(root, 0, str);
        if (operation == 2)
            output << getNumberOfWords(root, 0, str) << '\n';
        if (operation == 3)
            output << getLengthOfPrefix(root, 0, str) << '\n';
    }
    
    input.close();
    output.close();
    
    return 0;
}