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

const int
CHAR = 'z' - 'a' + 1;


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

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

    Arbore* operator [] (std::string str)
    {
        Arbore* curent = this;

        for (char chr: str)
        {
            Arbore* urmatorul = (*curent)[chr];
            if (!urmatorul->tata)
            {
                urmatorul->tata = curent;
                urmatorul->muchie = chr;
            }
            curent = urmatorul;
        }
        return curent;
    }

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



    inline int vezi_aparitii(std::string str)
    {
        Arbore* arb = (*this)[str];
        int rt = arb->aparitii;
        if (!rt)
            arb->pop();
        return rt;
    }
    inline void incrementeaza(std::string str)
    {
        (*this)[str]->aparitii++;
    }
    inline void decrementeaza(std::string str)
    {
        Arbore* arb = (*this)[str];
        if (!--arb->aparitii)
            arb->pop();
    }
    inline std::string prefix(std::string str)
    {
        Arbore* arb = (*this)[str];
        if (arb->subarbori.size() || arb->aparitii)
            return str;
        if (!arb->aparitii)
            arb->pop();
        return prefix(str.substr(0, str.size()-1));
    }

} arbore;



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