#include <bits/stdc++.h>

using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");
struct Trie
{
    int nrfii,nrcuv;
    Trie *fiu[26];
    Trie()
    {
        nrfii=nrcuv=0;
        memset(fiu,0,sizeof(fiu));
    }
};
Trie *root=new Trie;
char cuv[22];
void adauga(Trie *nod,int poz)
{
    if(cuv[poz]==0) nod->nrcuv++;
    else
    {
        int ch=cuv[poz]-'a';
        if(nod->fiu[ch]==0)
        {
            nod->nrfii++;
            nod->fiu[ch]=new Trie;
        }
        adauga(nod->fiu[ch],poz+1);
    }
}
bool sterge(Trie *nod,int poz)
{
    int ch=cuv[poz]-'a';
    if(cuv[poz]==0)
    {
        nod->nrcuv--;
    }
    else if(sterge(nod->fiu[ch],poz+1)==1)
    {
        nod->nrfii--;
        nod->fiu[ch]=0;
    }
    if(nod!=root && nod->nrfii==0 && nod->nrcuv==0)
    {
        delete nod;
        return 1;
    }
    return 0;
}
int aparitii(Trie *nod)
{
    for(int i=0;;i++)
    {
        if(nod==0) return 0;
        if(cuv[i]==0) return nod->nrcuv;
        nod=nod->fiu[cuv[i]-'a'];
    }
}
int prefix(Trie *nod)
{

    int i;
    for(i=0;;i++)
    {
        int ch=cuv[i]-'a';
        if(cuv[i]==0 || nod->fiu[ch]==0) return i;
        nod=nod->fiu[ch];
    }
}
int main()
{
    int op;
    while(fin>>op>>cuv)
    {
        op++;
        if(op==1) adauga(root,0);
        if(op==2) sterge(root,0);
        if(op==3) fout<<aparitii(root)<<"\n";
        if(op==4) fout<<prefix(root)<<"\n";
        memset(cuv,0,sizeof(cuv));
    }
}