#include <bits/stdc++.h>
using namespace std;
ifstream in("trie.in");
ofstream out("trie.out");
struct node
{
    char ch;
    int cuv;
    int capp;
    vector<node*> vec;
    node(char base_ch)
    {
        ch=base_ch;
        cuv=capp=0;
        vec.clear();
    }
};
int type;
string name;
bool first_time;
void add(node* nod,int ind)
{
    if(ind==name.size())
    {
        if(nod->capp==0)
            first_time=true;
        nod->capp++;
        if(first_time)
            nod->cuv++;
        return ;
    }
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==name[ind])
    {
        urm=x;
        break;
    }
    if(urm==NULL)
    {
        urm=new node(name[ind]);
        nod->vec.push_back(urm);
    }
    add(urm,ind+1);
    if(first_time)
        nod->cuv++;
}
bool delete_it;
void sub(node* nod,int ind)
{
    if(ind==name.size())
    {
        nod->capp--;
        if(nod->capp==0)
            nod->cuv--;
        if(nod->cuv==0)
            delete_it=true;
        return ;
    }
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==name[ind])
    {
        urm=x;
        break;
    }
    sub(urm,ind+1);
    if(delete_it)
        nod->cuv--;
    if(urm->cuv==0)
    {
        int where=-1;
        for(int i=0;i<nod->vec.size();++i)
        if(nod->vec[i]->ch==name[ind])
        {
            where=i;
            break;
        }
        nod->vec.erase(nod->vec.begin()+where);
    }
}
bool nowhere;
void app(node* nod,int ind)
{
    if(ind==name.size())
    {
        out<<nod->capp<<'\n';
        return ;
    }
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==name[ind])
    {
        urm=x;
        break;
    }
    if(urm==NULL)
    {
        out<<0<<'\n';
        nowhere=true;
        return ;
    }
    app(urm,ind+1);
}
void pre(node* nod,int ind)
{
    if(ind==name.size())
    {
        out<<ind<<'\n';
        return ;
    }
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==name[ind] and x->cuv>0)
    {
        urm=x;
        pre(urm,ind+1);
        return ;
    }
    out<<ind<<'\n';
}
int main()
{
    node* root=new node(' ');
    while(in>>type>>name)
    {
        if(type==0) first_time=false,add(root,0);
        else if(type==1) delete_it=false,sub(root,0);
        else if(type==2) nowhere=false,app(root,0);
        else pre(root,0);
    }
    return 0;
}