#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';

    }
    return 0;
}