#include <stdio.h>
#include<stdlib.h>
#define NRCH 26
FILE *fin;
typedef struct Nodul{
    int nrc, nrp;
    struct Nodul *fii[NRCH];
}Nod;
Nod *adauga(Nod *p, char ch){
    int i;
    if(p==NULL){
        p=(Nod*)malloc(sizeof(Nod));
        p->nrc=0;
        p->nrp=0;
        for(i=0; i<NRCH; i++){
            p->fii[i]=NULL;//(*p).fii[i]
        }
    }
    p->nrp++;
    if(ch!='\n'){
        p->fii[ch-'a']=adauga(p->fii[ch-'a'], fgetc(fin));
    }else{
        p->nrc++;
    }
    return p;
}
Nod *sterge(Nod *p, char ch){
    p->nrp--;
    if(ch!='\n'){
        p->fii[ch-'a']=sterge(p->fii[ch-'a'], fgetc(fin));
    }else{
        p->nrc--;
    }
    if(p->nrp==0){
        free(p);
        p=NULL;
    }
    return p;
}
int cauta(Nod *p, char ch){
    if(p==NULL){
        while(ch!='\n'){
            ch=fgetc(fin);
        }
        return 0;
    }
    if(ch=='\n'){
        return p->nrc;
    }
    return cauta(p->fii[ch-'a'], fgetc(fin));
}
int pref(Nod *p, char ch){
    if((ch=='\n')||(p->fii[ch-'a']==NULL)){
        while(ch!='\n'){
            ch=fgetc(fin);
        }
        return 0;
    }
    return 1+pref(p->fii[ch-'a'], fgetc(fin));
}
int main(){
    Nod *r;
    char t;
    FILE *fout;
    fin=fopen("trie.in", "r");
    fout=fopen("trie.out", "w");
    r=NULL;
    t=fgetc(fin);
    fgetc(fin);
    while(t!=EOF){
        if(t=='0'){
            r=adauga(r, fgetc(fin));
        }else if(t=='1'){
            r=sterge(r, fgetc(fin));
        }else if(t=='2'){
            fprintf(fout, "%d\n", cauta(r, fgetc(fin)));
        }else{
            fprintf(fout, "%d\n", pref(r, fgetc(fin)));
        }
        t=fgetc(fin);
        fgetc(fin);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}