#include <fstream>
#include <string>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
struct nod{
  int cnt, children;
  nod* urm[26];
}*root;

void adauga(nod* q, string str)
{
    for(auto i : str)
    {
        if(q->urm[i-'a'] == NULL)
            q->urm[i-'a'] = new nod, q->children++;
        q = q->urm[i-'a'];
    }
    q->cnt++;
}

void sterge(nod* q, string str, int k = 0)
{
    if(k<str.size())
    {
        sterge(q->urm[str[k]-'a'],str,k+1);
        if(q->urm[str[k]-'a']->cnt == -1)
        {
            delete q->urm[str[k]-'a'];
            q->children--, q->urm[str[k]-'a'] = NULL;
        }
    }
    else q->cnt--;
    if(q->cnt || q->children) return;
    q->cnt = -1;
}

int getcnt(nod *q, string str)
{
    for(auto i : str)
    {
        if(q->urm[i-'a'] == NULL)
            return 0;
        q = q->urm[i-'a'];
    }
    return q->cnt;
}

int getpref(nod *q, string str, int pref = 0)
{
    if(pref == str.size() || q->urm[str[pref]-'a'] == NULL) return pref;
    q = q->urm[str[pref]-'a'];
    return getpref(q, str, pref+1);
}
int main()
{
    int x;
    string str;
    root = new nod;
    while(f>>x)
    {
        f>>str;
        if(x == 0)
            adauga(root, str);
        if(x == 1)
            sterge(root,str);
        if(x == 2)
            g<<getcnt(root, str)<<'\n';
        if(x == 3)
            g<<getpref(root, str)<<'\n';
    }
    return 0;
}