#include <stdio.h>
#include <stdlib.h>
#define nmax 30
using namespace std;
FILE *fin,*fout;
struct trie
{
    int ap=0,children=0;
    char info;
    trie *child[nmax]={0};
}*start;
void insert_ap(const char *,trie *);
void delete_ap(const char *,trie *);
void print_ap(const char *,trie *);
void print_pref(const char *,trie *,int);
int main()
{
    fin=fopen("trie.in","r");
    fout=fopen("trie.out","w");
    char str[25];
    start=new trie;
    start->info='0';
    while(fgets(str,25,fin))
    {
        switch(str[0])
        {
            case '0': insert_ap(str+1,start);break;
            case '1': delete_ap(str+1,start);break;
            case '2': print_ap(str+1,start);break;
            case '3': print_pref(str+1,start,0);break;
            default:return 0;
        }
    }
    return 0;
}
void insert_ap(const char *str,trie *nod)
{
    int urm=str[1]-'a';
    if(str[1]=='\n')
        {nod->ap++;return;}
    else
    {
        if(!nod->child[urm])
        {
            nod->child[urm]=new trie;
            nod->child[urm]->info=str[1];
            nod->children++;
        }
        insert_ap(str+1,nod->child[urm]);
    }
}
void delete_ap(const char *str,trie *nod)
{
    if(str[1]=='\n')
        nod->ap--;
    else if(nod->child[str[1]-'a'])
    {
        delete_ap(str+1,nod->child[str[1]-'a']);
        if(!nod->child[str[1]-'a']->children && !nod->child[str[1]-'a']->ap)
            nod->child[str[1]-'a']=0;
    }
}
void print_ap(const char *str,trie *nod)
{
    if(str[1]=='\n')
        {fprintf(fout,"%d\n",nod->ap);return;}
    if(!nod->child[str[1]-'a'])
        {fprintf(fout,"%d\n",0);return;}
    print_ap(str+1,nod->child[str[1]-'a']);
}
void print_pref(const char *str,trie *nod, int nr)
{
    if(str[1]=='\n')
        fprintf(fout,"%d\n",nr);
    else if(!nod->child[str[1]-'a'])
        fprintf(fout,"%d\n",nr);
    else if(nod->child[str[1]-'a']->info!=str[1])
        print_pref(str+1,nod->child[str[1]-'a'],nr);
    else
       print_pref(str+1,nod->child[str[1]-'a'],nr+1);
}