#include <bits/stdc++.h>
using namespace std;
struct trie
{
    int ct,nrf;
    trie *fii[26];
    trie()
    {
        nrf=ct=0;
        memset( fii, 0, sizeof( fii ) );
    }
};
trie *t=new trie;
void ins(trie *nod,string s,int ct)
{
    if (ct==s.size())
    {
        nod->ct++;
        return;
    }
    if (nod->fii[(s[ct]-'a')]==0)
    {
        nod->fii[(s[ct]-'a')]=new trie;
        nod->nrf++;
    }
    ins(nod->fii[(s[ct]-'a')],s,ct+1);
}
bool del(trie *nod,string s,int ct)
{
    if (ct==s.size())
        nod->ct--;
    else if (del(nod->fii[s[ct]-'a'],s,ct+1))
    {
        nod->fii[(s[ct]-'a')]=0;
        nod->nrf--;
    }
    if (nod->ct==0 && nod->nrf==0 && nod!=t)
    {
        delete nod;
        return 1;
    }
    return 0;
}
int que(trie *nod,string s,int ct)
{
    if (ct==s.size())
        return nod->ct;
    if (nod->fii[s[ct]-'a'])
        return que(nod->fii[s[ct]-'a'],s,ct+1);
    return 0;
}
int pre(trie *nod,string s,int ct)
{
    if (ct==s.size() || nod->fii[s[ct]-'a']==0)
        return ct;
    return pre(nod->fii[s[ct]-'a'],s,ct+1);
}
int main()
{
    ifstream f ("trie.in");
    ofstream g ("trie.out");
    string s;
    int x;
    while (f>>x)
    {
        f>>s;
        if (x==0)
        {
            ins(t,s,0);
        }
        if (x==1)
        {
            del(t,s,0);
        }
        if (x==2)
        {
            g<<que(t,s,0)<<'\n';
        }
        if (x==3)
        {
            g<<pre(t,s,0)<<'\n';
        }
    }
}