//Andru Stefanescu
#include <bits/stdc++.h>
#define c (f >> query >> str)
using namespace std;
const int sigma = 'z'-'a'+1;
string str;
struct trie
{
    int sons,val;
    trie *son[sigma];
    trie()
    {
        val = 0;
        sons = 0;
        memset(son,NULL,sizeof(son));
    }
};
inline void citire(trie *nod,int p)
{
    if (p==str.size())
    {
        nod -> val++;
        return ;
    }
    int vaL=str[p]-'a';
    if (nod -> son[vaL] == NULL)
        nod -> son[vaL]=new trie , nod -> sons++;
    citire(nod->son[vaL],p+1);
    return ;
}
inline void stergere(trie *nod,int p)
{
    if (p==str.size())
    {
        nod->val--;
        return ;
    }
    int vaL=str[p]-'a';
    stergere(nod->son[vaL],p+1);
    if (nod->son[vaL]->val==0&&nod->son[vaL]->sons==0)
        nod->son[vaL]=NULL,nod->sons--;
    return ;
}
inline int numarare(trie *nod,int p)
{
    if (str.size()==p)
    {
        return nod -> val;
    }
    int vaL=str[p]-'a';
    if (nod -> son[vaL]==NULL)return 0;
    return (numarare(nod->son[vaL],p+1));
}
inline int prefix(trie *nod,int p)
{
    int vaL=str[p]-'a';
    if (p==str.size() || nod -> son[vaL] == NULL)
        return p;
    return (prefix(nod->son[vaL],p+1));
}
int main()
{
    ifstream f("trie.in");
    ofstream g("trie.out");
    trie *radacina ;
    int query;
    radacina = new trie;
    f >> query >> str;
    do
    {
        if (query == 0)
        {
            citire(radacina,0);
            c;
            continue;
        }
        if (query == 1)
        {
            stergere(radacina,0);
            c;
            continue ;
        }
        if (query == 2)
        {
            g << numarare(radacina,0) << '\n';
            c;
            continue ;
        }
        if (query == 3)
        {
            g << prefix(radacina,0) << '\n';
            c;
            continue ;
        }
    }
    while(!f.eof());

    return 0;
}