#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");
struct nod
{
    int nra;
    int nrf;
    nod *f[26];
    nod* parinte;
    nod()
    {
        int i;
        nra=0;
        nrf=0;
        parinte=NULL;
        for(i=0; i<26; i++)
            f[i]=NULL;
    }
};
string cuv;
void adauga(nod *p,int poz)
{
    int c;
    if(poz!=cuv.size())
    {
        c=(int) (cuv[poz]-'a');

        if(p->f[c]==NULL)
        {
            p->f[c]=new nod;
            p->f[c]->parinte=p;
            p->nrf++;
        }
        adauga(p->f[c],poz+1);
    }
    else
    {
        p->nra++;
    }
}
void stergere(nod *p,int poz)
{
    int c;
    nod *q;
    if(poz!=cuv.size())
    {
        c=(int) (cuv[poz]-'a');
        stergere(p->f[c],poz+1);
    }
    else
        p->nra--;
    if(p->nra==0&&p->nrf==0&&poz!=0)
    {
        c=(int) (cuv[poz-1]-'a');
        q=p->parinte;
        q->nrf--;
        q->f[c]=NULL;
        delete p;
    }
}
void afisare(nod *p,int poz)
{
    int c;
    if(poz!=cuv.size())
    {
        c=(int) (cuv[poz]-'a');
        if(p->f[c]==NULL)
        {
            fout<<0<<'\n';
        }
        else
        {
            afisare(p->f[c],poz+1);
        }
    }
    else
    {
        fout<<p->nra<<'\n';
    }
}
int prefix(nod *p,int poz)
{
    int c;
    if(poz!=cuv.size())
    {
        c=(int) (cuv[poz]-'a');
        if(p->f[c]==NULL)
        {
            return poz;
        }
        else
        {
            return prefix(p->f[c],poz+1);
        }
    }
    else
        return poz;
}
int main()
{
    nod *r;
    int cod;
    r=new nod;
    while(fin>>cod>>cuv)
    {
        if(cod==0)
        {
            adauga(r,0);
        }
        else if(cod==1)
        {
            stergere(r,0);
        }
        else if(cod==2)
        {
            afisare(r,0);
        }
        else if(cod==3)
        {
            fout<<prefix(r,0)<<'\n';
        }
    }
}