#include<stdio.h>
#include<cstring>
using namespace std;
struct nod
{
    int nrcuv;                  //nr de cuvinte care se termina in nodul curent
    int nrfii;                     //nr de cuvinte care au acest prefix,adica trec prin nodul curent
    nod *v[26];                //pt fiecare litera a alfabetului
    nod()
    {
        nrfii=nrcuv=0;
        memset(v,0,sizeof(v));
    }
};
nod *T=new nod;
void insereaza(nod *t,char s[21],int i)
{
    if(i == strlen(s))
        {
            t->nrcuv++;
            return ;
        }
    if(t->v[s[i] - 'a'] == 0)
    {
        t->v[s[i] - 'a']=new nod;
        t->nrfii++;
    }
    insereaza(t->v[s[i] - 'a'],s,i+1);
}
int sterge(nod *t,char s[21],int i)
{
    if(i == strlen(s))
        t->nrcuv--;
    else if(sterge(t->v[s[i] - 'a'],s,i + 1))
                {
                    t->v[s[i] - 'a']=0;
                    t->nrfii--;
                }

             if(!t->nrcuv && !t->nrfii  && t!=T)
                    {
                        delete t;
                        return 1;
                    }
    return 0;
}
int numar_cuvinte(nod *t,char s[21],int i)
{
    if(i == strlen(s))
        return t->nrcuv;
    if(t->v[s[i] - 'a'])
        return numar_cuvinte(t->v[s[i] - 'a'],s,i + 1);
    return 0;
}
int numar_fii(nod *t,char s[21],int i)
{
    if(i == strlen(s) || !t->v[s[i] - 'a'])
        return i;
    return numar_fii(t->v[s[i] - 'a'],s,i+1);
}
int main()
{
    FILE *f=fopen("trie.in","rt");
    FILE *g=fopen("trie.out","wt");
    int op;
    char cuv[21];
    while(!feof(f))
    {
        fscanf(f,"%d %s",&op,cuv);
        if(op==0)
            insereaza(T,cuv,0);
            else if(op==1)
                        sterge(T,cuv,0);
                        else if(op==2)
                                    fprintf(g,"%i\n",numar_cuvinte(T,cuv,0));
                                else fprintf(g,"%i\n",numar_fii(T,cuv,0));
        }
    }
    fclose(f);
    fclose(g);
    return 0;
}