#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

struct nod
{
    int cuv,nr_plozi;
    nod *plozi[30];
    nod()
    {
        nr_plozi=0;
        cuv=0;
        memset(plozi,0,sizeof(plozi));
    }


};
 nod *st = new nod();

void adaugare(char *p,nod *x)
{
    int k=p[0]-'a';
    if(p[0]=='\0')
    {
        x->cuv++;
        return;
    }
    if(x->plozi[k]==0)
    {
        x->plozi[k]=new nod();
        x->nr_plozi++;
    }
    adaugare(p+1,x->plozi[k]);
}

void stergere(char *p,nod *x)
{
    int k=p[0]-'a';
    if(p[0]=='\0')
        return;
    if(p[1]=='\0')
    {
        if(x->plozi[k]->cuv)
           x->plozi[k]->cuv--;
        if(!x->plozi[k]->nr_plozi && !x->plozi[k]->cuv && x!=st)
        {

            delete x->plozi[k];
            x->plozi[k]=NULL;
            x->nr_plozi--;
        }
        return;
    }
    stergere(p+1,x->plozi[k]);

    if(!x->plozi[k]->nr_plozi && !x->plozi[k]->cuv&& x!=st)
    {
        delete x->plozi[k];
        x->plozi[k]=NULL;
        x->nr_plozi--;
    }


}

void tiparire(char *p,nod *x)
{
    int k=p[0]-'a';
    if(p[0]=='\0')
    {
        printf("%d\n",x->cuv);
        return;
    }
    if(!x->plozi[k])
    {
        printf("0\n");
        return;
    }
    tiparire(p+1,x->plozi[k]);

}

int prefix(char *p,nod *x)
{
    int k=p[0]-'a';
    if(p[0]=='\0')
        return 0;

    if(!x->plozi[k])
        return 0;

    return 1+prefix(p+1,x->plozi[k]);

}



    char s[10000];
void citire()
{
    ifstream fin("trie.in");

    while(fin.getline(s,10000))
    {
        char a=s[0];
        strcpy(s,s+2);
        if(a=='0')
            adaugare(s,st);
        else if(a=='1')
            stergere(s,st);
        else if(a=='2')
            tiparire(s,st);
        else if(a=='3')
            printf("%d\n",prefix(s,st));
    }
}


int main()
{
    freopen("trie.out","w",stdout);
    citire();
    return 0;
}