#include <iostream>
#include <string>
#include <fstream>
#include <unordered_map>
#include <sstream>

using namespace std;

class TrieNode {
public:
    // Copiii nodului curent
    unordered_map<char, TrieNode*> children;
    // Numarul de aparitii ale cuvantului (pentru nodurile finale)
    int count;

    TrieNode() {
        count = 0;
    }
};

class Trie {
private:
    TrieNode* root;

    // Metoda recursiva pentru stergerea unui cuvant din trie
    bool removeHelper(TrieNode* node, string& word, int level) {
        if (node) { // Daca nodul curent nu este null
            if (level == word.length()) { // Daca am ajuns la finalul cuvantului
                if (node->count > 0) { // Daca in urma stergerii aparitiei cuvantul ramane in trie
                    node->count--;
                    return true;
                }
                return false;
            }

            char nextChar = word[level];
            if (node->children.find(nextChar) != node->children.end()) { // Daca nodul urmator exista
                TrieNode* nextNode = node->children[nextChar];
                bool shouldDeleteNode = removeHelper(nextNode, word, level + 1); // Testam daca dorim sa il stergem

                if (shouldDeleteNode) {
                    if (nextNode->count == 0 && nextNode->children.empty()) { // Daca nodul nu reprezinta finalul altui cuvant si e frunza 
                        delete nextNode; // Il stergem
                        node->children.erase(nextChar);
                    }
                    return node->children.empty(); // Daca nodul curent nu mai are copii, am vrea sa il stergem si pe acesta
                }
            }
        }
        return false;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* current = root;
        // Parcurgem cuvantul si adaugam noduri noi daca este nevoie
        for (char c : word) {
            if (current->children.find(c) == current->children.end()) {
                current->children[c] = new TrieNode();
            }
            current = current->children[c];
        }
        // Cresc nr de aparitii
        current->count++;
    }

    void remove(string word) {
        if (word.empty())
            return;
        // Sterg folosind removeHelper de mai sus
        removeHelper(root, word, 0);
    }

    int search(string word) {
        TrieNode* current = root;
        // Parcurg cuvantul si ma opresc daca nu gasesc nod
        for (char c : word) {
            if (current->children.find(c) == current->children.end()) {
                return 0;
            }
            current = current->children[c];
        }
        // Intorc numarul de aparitii
        return current->count;
    }

    int longestPrefix(string word) {
        TrieNode* current = root;
        int length = 0;
        // Parcurg cuvantul si ma opresc daca nu gasesc nod
        for (char c : word) {
            if (current->children.find(c) == current->children.end()) {
                break;
            }
            current = current->children[c];
            length++;
        }
        return length;
    }
};

int main() {
    Trie trie;

    ifstream fin("trie.in");
    ofstream fout("trie.out");

    string line;
    while(getline(fin, line)) {
        istringstream iss(line);
        int command;
        string word;
        iss >> command >> word;
        switch(command) {
            case 0:
                trie.insert(word);
                break;
            case 1:
                trie.remove(word);
                break;
            case 2:
                fout << trie.search(word) << endl;
                break;
            case 3:
                fout << trie.longestPrefix(word) << endl;
                break;
            default:
                break;
        }
    }

    // trie.insert("latitudine");
    // cout << trie.longestPrefix("lati") << endl;
    // trie.remove("latitudine");
    // cout << trie.longestPrefix("lati") << endl;
    return 0;
}