/*
 * =====================================================================================
 *
 *       Filename:  trie.cpp
 *
 *    Description:  
 *
 *        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 <cstdio>
#include <fstream>
#include <cstring>

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);
    }
};


void pushToTrie(Trie* word, int letter) {
    if (letter == str.size()) {
        word->count_words++;
        return;
    }
    if (word->child[str[letter] - 'a'] == NULL) {
        word->child[str[letter] - 'a'] = new Trie;
        word->count_childs++;
    }

    pushToTrie(word->child[str[letter] - 'a'], letter + 1);
}

bool popFromTrie(Trie* word, int letter) {
    if (letter == str.size()) {
        word->count_words--;
    } else {
        if (popFromTrie(word->child[str[letter] - 'a'], letter + 1) == 1) {
            word->count_childs--;
            word->child[str[letter] - 'a'] = NULL;
        }
    }

    if (word->count_childs == 0 && 
        word->count_words == 0  
        /*word != 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 word;
        return 1;
    }

    return 0;
}

int getNumberOfWords(Trie* word, int letter) {
    if (letter == str.size()) 
        return word->count_words;

    if (word->child[str[letter] - 'a'] != NULL) 
        return getNumberOfWords(word->child[str[letter] - 'a'], 
                                letter + 1);

    return 0;
}

int getNumberOfPrefixes(Trie* word, int letter) {
    if (letter == str.size() || word->child[str[letter] - 'a'] == NULL)
        return letter;

    return getNumberOfPrefixes(word->child[str[letter] - 'a'], letter + 1);
}

int main() {
    int operation; 
    ifstream input("trie.in");
    ofstream output("trie.out");

    Trie* 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;
}