/*
 * =====================================================================================
 *
 *       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) {
    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) {
    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) {
    if (letter == str.size()) // we have erached 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; 

    return getNumberOfWords(node->child[str[letter] - 'a'], 
                            letter + 1); // continue with the next letter
}
  
int getNumberOfPrefixes(Trie* node, int letter) {
    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);
        if (operation == 1)
            popFromTrie(root, 0);
        if (operation == 2) 
            output << getNumberOfWords(root, 0) << '\n';
        if (operation == 3)
            output << getNumberOfPrefixes(root, 0) << '\n';
    }
  
    input.close();
    output.close();
  
    return 0;
}