#include <cstring>
#include <fstream>
using namespace std;

ifstream f("trie.in");
ofstream g("trie.out");

struct nod{
    int fin = 0;
    int nrc = 0;

    nod *urm[30]{0};
}*root;

int type, l, last;
char cuv[30];

void add(nod *&p, int index)
{
    if(index == l)
    {
        p->fin ++;
        return;
    }
    if(!p->urm[cuv[index]-'a'])
    {
        p->urm[cuv[index]-'a'] = new nod;
    }
    p->nrc++;
    add(p->urm[cuv[index]-'a'], index+1);

}
bool ok = 1;
int del(nod *&p, int index)
{
    if(index == l)
    {
        p->fin --;
        if(p->fin == 0 && p->nrc == 0)
        {
            return 1;
            p = 0;
            delete p;
        }
        return 0;
    }
    if(del(p->urm[cuv[index]-'a'], index+1) == 1)
    {
        p->urm[cuv[index]-'a'] = 0;
        p->fin --;
        if(p->fin == 0 && p->nrc == 0 && p != root)
        {
            delete p;
            return 1;
        }
        return 0;
    }
}

void fr(nod *p, int index)
{
    if(index == l)
    {
        g<<p->fin<<'\n';
        return;
    }
    if(!p->urm[cuv[index]-'a'])
    {
        g<<"0\n";
        return;
    }
    fr(p->urm[cuv[index]-'a'], index+1);
}

void pref(nod *p, int index)
{
    if(!p)
        return;
    last = index;
    pref(p->urm[cuv[index]-'a'], index+1);
}

int main()
{
    root = new nod;
    while(f>>type>>cuv)
    {
        l = strlen(cuv);
        if(type == 0)
            add(root, 0);
        else if(type == 1)
            del(root, 0);
        else if(type == 2)
            fr(root, 0);
        else{
            pref(root, 0);
            g<<last<<'\n';
        }

    }
    return 0;
}