#define fisier "trie"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

#include <unordered_map>
#include <string>
struct Arbore
{
    std::unordered_map<char, Arbore*> subarbori;
    int aparitii = 0;
    Arbore* tata = NULL;
    char muchie = 0;

    void afiseaza(int ind)
    {
        std::string
        indent(4*ind, ' '),
        indent2 = indent + "    ";

        out
        << indent << "{\n"
        << indent2 << "aparitii = " << aparitii << ",\n"
        << indent2 << "tata = " << tata << ",\n"
        << indent2 << "muchie = " << (muchie? muchie: '0') << ",\n"
        << indent2 << "nr_subarbori = " << subarbori.size() << ",\n\n"
        << indent2 << "subarbori =\n" << indent2 << "[\n";
        for (auto pr: subarbori)
        {
            out << indent2 << "\'" << pr.first << "\':\n";
            pr.second->afiseaza(ind + 2);
            out << ",\n";
        }
        out << indent2 << "]\n" << indent << "}";
    }

    Arbore* operator [] (const char chr)
    {
        Arbore*& subarb = subarbori[chr];
        if (!subarb)
        {
            subarb = new Arbore;
            subarb->tata = this;
            subarb->muchie = chr;
        }
        return subarb;
    }

    Arbore* operator [] (std::string str)
    {
        Arbore* curent = this;
        for (char chr: str)
            curent = (*curent)[chr];
        return curent;
    }

    void pop()
    {
        if (!subarbori.size() && !aparitii && tata)
        {
            tata->subarbori.erase(muchie);
            tata->pop();
            delete this;
        }
    }



    inline int vezi_aparitii(std::string str)
    {
        Arbore* arb = (*this)[str];
        int rt = arb->aparitii;
        arb->pop();
        return rt;
    }
    inline void incrementeaza(std::string str)
    {
        (*this)[str]->aparitii++;
    }
    inline void decrementeaza(std::string str)
    {
        Arbore* arb = (*this)[str];
        --arb->aparitii;
        arb->pop();
    }
    inline int prefix(std::string str)
    {
        str += '#';
        //out << "PREFIX\n";
        Arbore* curent = this;
        for (int i = 0; str[i]; i++)
        {
            //out << "subarbori = " << subarbori.size() << "\n";
            //out << str[i] << " " << (curent->muchie?curent->muchie:'0') << " " << curent->aparitii << " " << curent->subarbori.size() << "\n";
            if (!curent->aparitii && !curent->subarbori.size())
            {
                curent->pop();
                return i - 1;
            }
            curent = (*curent)[str[i]];
        }

        return str.size();
    }

} arbore;



int main()
{
    int op;
    std::string cuv;
    while (in >> op >> cuv)
    {
        switch (op)
        {
            case 0:
                //out << ">>> incr " << cuv << "\n";
                arbore.incrementeaza(cuv);
                break;
            case 1:
                //out << ">>> decr " << cuv << "\n";
                arbore.decrementeaza(cuv);
                break;
            case 2:
                //out << ">>> apar " << cuv << "\n";
                out << arbore.vezi_aparitii(cuv) << '\n';
                break;
            case 3:
                //out << ">>> pref " << cuv << "\n";
                out << arbore.prefix(cuv) << '\n';
                break;
        }
    }
}