#include <bits/stdc++.h>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
int x;

class nod
{
    public:
    int nrfii,occ;
    nod *p[26];

    nod()
    {
        nrfii=occ=0;
        memset(p,0,sizeof(p));
    }
};

void Add(nod *root,string word,int k)
{
    if(k==word.size())
    {
        root->occ++;
        return ;
    }

    int idx=word[k]-'a';
    if( root->p[ idx ] == NULL )
    {
        root->nrfii++;

        nod *vertex=new nod;
        root->p[idx]=vertex;
    }

    Add(root->p[idx],word,k+1);
   // cout<<word<<' '<<k<<' '<<word[k]<<' '<<root->occ<<' '<<root->nrfii<<'\n';
}

int Erase(nod *root,string word,int k)
{
    if(k==word.size())
    {
        if( root->occ == 1 )
        {
            delete root;
            return 1;
        }
        else
        {
            root->occ--;
            return 0;
        }
    }

    int idx=word[k]-'a';


    if(Erase(root->p[idx],word,k+1))
    {//cout<<word<<' '<<k<<' '<<word[k]<<' '<<root->occ<<' '<<root->nrfii<<'\n';
        root->p[idx]=0;
        root->nrfii--;
        if(root->nrfii == 0 )
        {
            delete root;
            return 1;
        }
        else return 0;
    }

    return 0;

}

int Occurances(nod *root,string word,int k)
{
     if(k==word.size()) return root->occ;

     int idx=word[k]-'a';

     if( k<word.size() && root->p[idx] )
        return Occurances( root->p[idx],word,k+1 );
     else
        return 0;
}

int Prefix(nod* root,string word,int k)
{ cout<<k<<' '<<word<<' '<<word[k]<<'\n';
    int idx=word[k]-'a';
    if( k<word.size() && root->p[idx] )
        return 1+Prefix(root->p[idx],word,k+1);
    else
        return 0;
}

int main()
{
    nod* root=new nod;

    string S;

    while(f>>x>>S)
    {
        if(x==0) Add(root,S,0);
        else
        if(x==1)
        {
            bool ok=0;
            Erase(root,S,0);
        }
        else
        if(x==2) g<<Occurances(root,S,0)<<'\n';
        else
        g<<Prefix(root,S,0)<<'\n';

    }

    return 0;
}