#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
ifstream cin("trie.in");
ofstream cout("trie.out");

struct Trie {
    int cnt, nf;
    Trie *fiu[26];
    Trie() {
        cnt= nf= 0;
        memset(fiu,0,sizeof(fiu));
    }
};

Trie *T= new Trie;

void ins(Trie *nod, char *p)
{
    if(*p=='\0')
    {
        nod->cnt++;
        return ;
    }

    if(nod->fiu[*p-'a']==0)
    {
        nod->fiu[*p-'a']=new Trie;
        nod->nf++;
    }
    ins(nod->fiu[*p-'a'],p+1);
}

int del(Trie *nod, char *p)
{
    if(*p=='\0')
        nod->cnt--;
    else if(del(nod->fiu[*p-'a'],p+1))
    {
        nod->fiu[*p-'a']=0;
        nod->nf--;
    }

    if(nod->cnt==0 && nod->nf==0 && nod!=T)
    {
        delete nod;
        return 1;
    }
    return 0;
}

int que(Trie *nod, char *p)
{
    if(*p=='\0')
        return nod->cnt;
    if(nod->fiu[*p-'a']==0)
        return 0;
    return que(nod->fiu[*p-'a'],p+1);
}

int pre(Trie *nod, char *p, int k)
{
    if(*p=='\0' || nod->fiu[*p-'a']==0)
        return k;
    return pre(nod->fiu[*p-'a'],p+1,k+1);
}

int main()
{
    int op;
    char str[24];
    while(cin>>op>>str)
    {
        if(op==0)
            ins(T,str);
        else if(op==1)
            del(T,str);
        else if(op==2)
            cout<<que(T,str)<<'\n';
        else cout<<pre(T,str,0)<<'\n';
    }
    return 0;
}