#include <bits/stdc++.h>

using namespace std;
const string file="trie";
ifstream f(file+".in");
ofstream g(file+".out");
struct Nod{
    Nod* child[26];
    int nr;
};
void inser(Nod* p,string word)
{
    Nod* curent = p;
    for (auto c : word) {
        if(curent->child[c-'a']==NULL)
        {
            Nod* newnode =new Nod();
            curent->child[c-'a']=newnode;
        }
        curent=curent->child[c-'a'];
    }
    curent->nr++;
}
int caut(Nod* p, string word)
{
    Nod* curent=p;
    for(auto c : word)
    {
        if(curent->child[c-'a']==NULL) return false;
        curent=curent->child[c-'a'];
    }
    return curent->nr;
}
bool sterg(Nod* root,string word)
{
    Nod* curent=root;
    Nod* lastBranchNode=NULL;
    char lastBranchChar='a';
    for(auto c : word)
    {
        if(curent->child[c-'a']==NULL)return false;
        else
        {
            int x=0;
            for(int i=0;i<26;i++)
            {
                if(curent->child[i]!=NULL)
                    x++;
            }
            if(x>1)
            {
                lastBranchNode=curent;
                lastBranchChar=c;
            }
            curent=curent->child[c-'a'];
        }
    }
    int x=0;
    for(int i=0;i<26;i++)
    {
        if(curent->child[i]!=NULL)
            x++;
    }
    if(x>0)
    {
        curent->nr--;
        return true;
    }
    if(lastBranchNode != NULL)
    {
        lastBranchNode->child[lastBranchChar-'a']=NULL;
        return true;
    }
    else
    {
        root->child[word[0]]=NULL;
        return true;
    }
}
int prefi(Nod* p,string word)
{
    int cnt=0,sol=0;
    Nod* curent=p;
    for(auto c : word)
    {
        if(curent->child[c-'a']==NULL)return sol;
        else
        {
            cnt++;
            int x=0;
            for(int i=0;i<26;i++)
            {
                if(curent->child[i]!=NULL)
                    x++;
            }
            if(x>1) sol=cnt;
            curent=curent->child[c-'a'];
        }
    }
    return cnt;
}
int main()
{
    Nod* p=new Nod;
    int c;
    string s;
    while(f>>c>>s)
    {
        if(c==0) inser(p,s);
        else if(c==1) sterg(p,s);
        else if(c==2)g<<caut(p,s)<<'\n';
        else if(c==3)g<<prefi(p,s)<<'\n';
    }
    return 0;
}