/*
 * =====================================================================================
 *
 *       Filename:  IA_trie.cpp
 *
 *    Description:  http://www.infoarena.ro/problema/trie
 *
 *        Version:  1.0
 *        Created:  03/24/2016 10:50:30 AM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */

#include <iostream>
#include <string>
#include <map>
#include <fstream>

using namespace std;

struct TrieNode {
    int countWords; 
    map<char, TrieNode*> child;

    TrieNode() {
        countWords = 0;
    }
};

void pushToTrie(TrieNode* root, int letter, string& str) {
    if (root == NULL) {
        return;
    }
    if (letter == str.length()) {
        root->countWords++;
        return;
    }
    if (root->child.find(str[letter]) == root->child.end()) {
        root->child[str[letter]] = new TrieNode;
    }
    pushToTrie(root->child[str[letter]], letter + 1, str);
}

bool popFromTrie(TrieNode* root, TrieNode* rootNode, int letter, string& str) {
    if (root == NULL) {
        return false;
    }
    if (letter == str.length()) {
        root->countWords--;
    } else {
        if (root->child.find(str[letter]) != root->child.end() && 
            popFromTrie(root->child[str[letter]], 
                        rootNode, 
                        letter + 1,
                        str) == true) {
            root->child.erase(root->child.find(str[letter]));
        }
    }

    if (root->child.size() == 0 &&
        root->countWords == 0  &&
        root != rootNode) {

        delete root;
        return true;
    }
    return false;
}

int getNumberOfWords(TrieNode* root, int letter, string& str) {
    if (root == NULL) {
        return 0;
    }
    if (letter == str.length()) {
        return root->countWords;
    }
    if (root->child.find(str[letter]) == root->child.end()) {
        return 0;
    }

    return getNumberOfWords(root->child[str[letter]], letter + 1, str);
}

int getLengthOfPrefix(TrieNode* root, int letter, string& str) {
    if (root == NULL) {
        return 0;
    }
    if (letter == str.length() || root->child.find(str[letter]) == root->child.end()) {
        return letter;
    }

    return getLengthOfPrefix(root->child[str[letter]], letter + 1, str);
}

/*
bool isInTrie(TrieNode* root, string str) {
    if (root == NULL) {
        return false;
    }
    if (str.length() < 1) {
        cout << root->countWords << " ";
        return true;
    }
    if (root->child.find(str[0]) == root->child.end()) {
        return false;
    }
    return isInTrie(root->child[str[0]], str.substr(1, str.length()));
}
*/

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

    TrieNode* rootNode;
    rootNode = new TrieNode; 

    while (input >> operation >> str) {
        if (operation == 0) {
            pushToTrie(rootNode, 0, str);
        }
        if (operation == 1) {
            popFromTrie(rootNode, rootNode, 0, str);
        }
        if (operation == 2) {
            output << getNumberOfWords(rootNode, 0, str) << "\n";
        }
        if (operation == 3) {
            output << getLengthOfPrefix(rootNode, 0, str) << "\n";
        }
    } /* while */

    input.close();
    output.close(); 
    /*
    str = "lac";
    cout << (isInTrie(rootNode, str)? "yes": "no") << "\n";
    */

    return 0;
}