/*
 * =====================================================================================
 *
 *       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;
string str;
   
struct Trie {
    int count_childs, count_words;
    vector<Trie*> child;
   
    Trie() {
        count_childs = count_words = 0;
        child.resize(alphabet_size, NULL);
    }
};
   
Trie* root;
   
void pushToTrie(Trie* 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 Trie; // create the child with that character
        node->count_childs++;
    }
   
    pushToTrie(node->child[str[letter] - 'a'], letter + 1); // continue with the next character from word
}
 
bool popFromTrie(Trie* 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) == 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(Trie* 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
}
   
int getLengthOfPrefix(Trie* 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 getNumberOfPrefixes(node->child[str[letter] - 'a'], letter + 1); // otherwise go to the child with the next character
}
   
int main() {
    int operation;
    ifstream input("trie.in");
    ofstream output("trie.out");
   
    root = new Trie;
   
    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;
}