#include <cstring>
#include <fstream>
#define CH (*s-'a')
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
int x;
char v[32];
struct Trie
{
    int cnt=0, nrfii=0;
    Trie *fiu[32]={0};
};
Trie *T = new Trie;
void ins(Trie *nod, char *s)
{
    if(*s==NULL)
        {
            nod->cnt++;
            return;
        }
    if(nod->fiu[CH]==0)
    {
        nod->fiu[CH]=new Trie;
        nod->nrfii++;
    }
    ins(nod->fiu[CH],s+1);
}
int del(Trie *nod, char *s)
{
    if(*s==NULL)
        nod->cnt--;
    else if(del(nod->fiu[CH],s+1))
    {
        nod->fiu[CH]=0;
        nod->nrfii--;
    }
    if(nod->cnt==0 && nod->nrfii==0 && nod!=T)
    {
        delete nod;
        return 1;
    }
    return 0;
}
int que(Trie *nod, char *s)
{
    if(*s==NULL)
        return nod->cnt;
    if(nod->fiu[CH])
        return que(nod->fiu[CH],s+1);
    return 0;
}
int pre(Trie *nod, char *s, int k)
{
    if(*s==NULL || nod->fiu[CH]==0)
        return k;
    return pre(nod->fiu[CH],s+1,k+1);
}
int main()
{
    while(f>>x>>v)
    {
        switch(x)
        {
            case 0: ins(T,v); break;
            case 1: del(T,v); break;
            case 2: g<<que(T,v)<<'\n'; break;
            case 3: g<<pre(T,v,0)<<'\n'; break;
        }
    }
}