#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 uu=0,ix;
            int in=0;
            int cn=0; ///nodul curent
            while(in<s.size())
            {
                int un=-1,iq;
                for(auto a:v[cn])
                {
                    if(cr[a]==int(s[in]))
                    {
                        if(in==0)
                        {
                            ix=a;
                        }
                        iq=a;
                        un=a;
                        break;
                    }
                }
                if(v[cn].size()>=2 || f[cn]>=1)
                {
                    uu=cn;
                    ix=iq;
                }
                if(un==-1)
                {
                    cn=0;
                    break;
                }
                cn=un;
                ++in;
            }
            f[cn]--;
            if(f[cn]==0 && v[cn].size()==0)
            {
                v[uu].erase(ix);
            }
}

        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;
}