#include <fstream>
using namespace std;
ifstream in("trie.in");
ofstream out("trie.out");
string s,s0;
struct nod
{
    int info;
    nod *urm[26],*prec[26];
};
nod *prim;
void adaug(nod* &first,string s)
{
    int ok=0;
    if(first==NULL)
    {
        first=new nod;
        for(int i=0; i<26; i++)
            first->prec[i]=first->urm[i]=NULL;
    }
    nod *aux=first;
    for(int i=0; i<s.size(); i++)
    {
        if(aux->urm[s[i]-'a']==NULL)
        {
            ok=1;
            nod *aux2;
            for(int j=i; j<s.size(); j++)
            {
                aux2=new nod;
                for(int k=0; k<26; k++)
                    aux2->urm[k]=NULL;
                aux->urm[s[j]-'a']=aux2;
                if(j!=0)
                    aux2->prec[s[j-1]-'a']=aux;
                aux=aux2;
            }
            if(ok==0)
                aux->info++;
            break;
        }
        else
            aux=aux->urm[s[i]-'a'];
    }
    aux->info++;
}
void scoate(nod* &first,string s)
{
    nod *aux=first;
    for(int i=0; i<s.size(); i++)
        aux=aux->urm[s[i]-'a'];
    if(aux->info>=2)
        aux->info--;
    else
    {
        aux->info--;
        nod *aux2;
        for(int i=s.size()-1; i>=0&&!aux->info; i--)
        {
            if(i!=0)
                aux2=aux->prec[s[i-1]-'a'];
            else
                aux2=first;
            aux2->urm[s[i]-'a']=NULL;
            delete(aux);
            aux=aux2;
        }
    }
}
void afiseaza(nod* &first,string s)
{
    nod *aux=first;
    for(int i=0; i<s.size(); i++)
        aux=aux->urm[s[i]-'a'];
    out<<aux->info<<'\n';
}
void prefix(nod* &first,string s)
{
    nod *aux=first;
    int max1=0,cnt=0;
    for(int i=0; i<s.size(); i++)
    {
        if(aux->info)
            max1=cnt;
        aux=aux->urm[s[i]-'a'];
        cnt++;
    }
    if(aux->info!=1)
        out<<cnt<<'\n';
    else
        out<<max1<<'\n';
}
int main()
{
    int t;
    in>>t>>ws>>s;
    while(s!=s0)
    {
        if(t==0)
            adaug(prim,s);
        else if(t==1)
            scoate(prim,s);
        else if(t==2)
            afiseaza(prim,s);
        else
            prefix(prim,s);
        s0=s;
        in>>t>>ws>>s;
    }
    return 0;
}