#include <cstring>
#include <stdio.h>
using namespace std;
struct nod
{
    int nrfii;
    int nrcuv;
    nod *v[26];
    nod()
    {
        int i;
        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,"%i %s",&op,&cuv);
        switch(op)
        {
            case 0:insereaza(T,cuv,0);break;
            case 1:sterge(T,cuv,0);break;
            case 2:fprintf(g,"%i\n",numar_cuvinte(T,cuv,0));break;
            case 3:fprintf(g,"%i\n",numar_fii(T,cuv,0));break;
        }
    }
    fclose(f);
    fclose(g);
    return 0;
}