#include <bits/stdc++.h>
using namespace std;
ifstream in("trie.in");
ofstream out("trie.out");
struct node
{
    int dp;
    int cap;
    char ch;
    vector<node*> vec;
};
int t;
string s;
void add(node* nod,int ind)
{
    nod->dp++;
    if(ind==s.size())
    {
        nod->cap++;
        return ;
    }
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==s[ind])
    {
        urm=x;
        break;
    }
    if(urm==NULL)
    {
        urm=new node;
        urm->dp=0;
        urm->cap=0;
        urm->ch=s[ind];
        urm->vec.clear();
        nod->vec.push_back(urm);
    }
    add(urm,ind+1);
}
void elim(node* nod,int ind)
{
    nod->dp--;
    if(ind==s.size())
    {
        nod->cap--;
        return ;
    }
    node* urm=NULL;
    int poz=0;
    for(node* x:nod->vec)
    {
        if(x->ch==s[ind])
        {
            urm=x;
            break;
        }
        ++poz;
    }
    elim(urm,ind+1);
    if(urm->dp==0)
        nod->vec.erase(nod->vec.begin()+poz);
}
int app(node* nod,int ind)
{
    if(ind==s.size())
        return nod->cap;
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==s[ind])
    {
        urm=x;
        break;
    }
    if(urm==NULL)
        return 0;
    return app(urm,ind+1);
}
int lpr(node* nod,int ind)
{
    if(ind==s.size())
        return ind;
    node* urm=NULL;
    for(node* x:nod->vec)
    if(x->ch==s[ind])
    {
        urm=x;
        break;
    }
    if(urm==NULL)
        return ind;
    return lpr(urm,ind+1);
}
void df(node* nod)
{
    out<<"---\n";
    out<<"dp: "<<nod->dp<<'\n';
    out<<"cap: "<<nod->cap<<'\n';
    out<<"ch: "<<nod->ch<<'\n';
    out<<nod->vec.size()<<" vec"<<'\n';
    for(node* x:nod->vec)
        df(x);
}
int main()
{
    node* root=new node;
    root->dp=1;
    root->cap=1;
    root->ch=' ';
    root->vec.clear();
    while(in>>t)
    {
        in>>s;
        if(t==0)
            add(root,0);
        else if(t==1)
            elim(root,0);
        else if(t==2)
            out<<app(root,0)<<'\n';
        else if(t==3)
            out<<lpr(root,0)<<'\n';
        //df(root);
    }
    return 0;
}