#include <bits/stdc++.h>
using namespace std;
#define op(s) ifstream fin(s+string(".in"));ofstream fout(s+string(".out"))
#define ch(s) s-'a'
struct trie{
    int cnt, nrfii;
    trie *fiu[26];
    trie()
    {
        cnt = nrfii = 0;
        memset(fiu, 0, sizeof(fiu));
    }
};
trie *t = new trie;
char lin[50];
void ins(trie *nod, char* s)
{
    if(*s=='\0')
    {
        nod->cnt++;
        return;
    }
    if(nod->fiu[ch(s[0])]==0)
    {
        nod->fiu[ch(s[0])] = new trie;
        nod->nrfii++;
    }
    ins(nod->fiu[ch(s[0])],s+1);
}
int del(trie *nod, char *s)
{
    if(*s=='\0')nod->cnt--;
    else if(del(nod->fiu[ch(s[0])],s+1))
    {
        nod->fiu[ch(s[0])]=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=='\0')return nod->cnt;
    if(nod->fiu[ch(s[0])])return que(nod->fiu[ch(s[0])],s+1);
    return 0;
}
int pre(trie *nod, char *s, int k)
{
    if(*s=='\0'||nod->fiu[ch(s[0])]==0)return k;
    return pre(nod->fiu[ch(s[0])],s+1,k+1);
}
int main()
{
    op("trie");
    int nr=0;
    while(fin.getline(lin,50))
    {
        if(lin[0]=='0')ins(t,lin+2);
        else if(lin[0]=='1')del(t,lin+2);
        else if(lin[0]=='2')fout<<que(t,lin+2)<<'\n';
        else if(lin[0]=='3')fout<<pre(t,lin+2,0)<<'\n';
        else break;
    }
    return 0;
}