#include <fstream>
#include <cstring>
using namespace std;
int a[100010][30],cuv[100010],fr[100010],nr,n;
string s;
void adauga(int nod,int p)
{
    if(nod!=1) fr[nod]++;
    if(p==s.size()) {cuv[nod]++; return; }
    if(a[nod][s[p]-'a'+1]) adauga(a[nod][s[p]-'a'+1],p+1);
    else
    {
        a[nod][s[p]-'a'+1]=++nr;
        adauga(nr,p+1);
    }
}
void sterge(int nod,int p)
{
    if(nod!=1) fr[nod]--;
    if(p==s.size()) cuv[nod]--;
    if(p==s.size()) return;
    if(a[nod][s[p]-'a'+1])
    {
        sterge(a[nod][s[p]-'a'+1],p+1);
        if(!fr[a[nod][s[p]-'a'+1]]) a[nod][s[p]-'a'+1]=0;
    }
}
int aparitii(int nod, int p)
{

    if(p==s.size()) return cuv[nod];
    if(a[nod][s[p]-'a'+1]) return aparitii(a[nod][s[p]-'a'+1],p+1);
    return 0;
}
int prefix(int nod, int p)
{
    if(p==s.size()) return p;
    if(a[nod][s[p]-'a'+1]) return prefix(a[nod][s[p]-'a'+1],p+1);
    return p;
}
int main()
{
    ifstream fi("trie.in");
    ofstream fo("trie.out");
    nr=1;
    while(fi>>n>>s)
    {
        if(n==0) adauga(1,0);
        if(n==1) sterge(1,0);
        if(n==2) fo<<aparitii(1,0)<<"\n";
        if(n==3) fo<<prefix(1,0)<<"\n";
    }

    return 0;
}