#include <bits/stdc++.h>

using namespace std;

string s;

set <int> v[1000055];

int cr[1000055];

int f[1000055],nd=0;

int main()
{
    ifstream cin("trie.in");
    ofstream cout("trie.out");
    int caz;
    while(cin>>caz)
    {
        cin>>s;
        if(caz==0)
        {
            int in=0;
            int cn=0; ///nodul curent
            while(in<s.size())
            {
                int un=-1;
                for(auto a:v[cn])
                {
                    if(cr[a]==int(s[in]))
                    {
                        un=a;
                        break;
                    }
                }
                if(un==-1)
                {
                    ++nd;
                    v[cn].insert(nd);
                    cr[nd]=int(s[in]);
                    un=nd;
                }
                cn=un;
                ++in;
            }
            f[cn]++;
        }
else if (caz == 1)
{
    int in = 0;
    int cn = 0;
    vector<pair<int, int>> path; // (părinte, nod curent)

    while (in < s.size())
    {
        int un = -1;
        for (auto a : v[cn])
        {
            if (cr[a] == s[in])
            {
                path.push_back({cn, a}); // Salvăm drumul pentru eventuală ștergere
                un = a;
                break;
            }
        }
        if (un == -1)
        {
            cn = 0;
            break;
        }
        cn = un;
        ++in;
    }

    if (f[cn] > 0)
        f[cn]--;

    // Curățăm nodurile goale de la final spre început
    if (f[cn] == 0)
    {
        for (int i = int(path.size()) - 1; i >= 0; --i)
        {
            int parent = path[i].first;
            int child = path[i].second;

            if (f[child] == 0 && v[child].empty())
            {
                v[parent].erase(child);
            }
            else
            {
                break;
            }
        }
    }
}

        else if(caz==2)
        {
           // cout<<caz<<" ";
            int in=0;
            int cn=0; ///nodul curent
            while(in<s.size())
            {
                int un=-1;
                for(auto a:v[cn])
                {
                    if(cr[a]==int(s[in]))
                    {
                        un=a;
                        break;
                    }
                }
                if(un==-1)
                {
                    cn=0;
                    break;
                }
                cn=un;
                ++in;
            }
            cout<<f[cn]<<"\n";
        }
        else
        {
           // cout<<caz<<" ";
            int mx=0;
            int in=0;
            int cn=0; ///nodul curent
            while(in<s.size())
            {
                int un=-1;
                for(auto a:v[cn])
                {
                    if(cr[a]==int(s[in]))
                    {
                        un=a;
                        break;
                    }
                }
                if(un==-1)
                {
                    mx=in;
                    cn=0;
                    break;
                }
                cn=un;
                ++in;
            }
            if(in==s.size())
            {
                mx=in;
            }
            cout<<mx<<"\n";
        }
    }
    return 0;
}