#include <fstream>
#include <cstring>
#include <iostream>

using namespace std;

ifstream in("trie.in");
ofstream out("trie.out");

struct node
{
    int cnt, fii;
    node* v[26];
    node()
    {
        cnt = 0;
        fii = 0;
        for(int i = 0; i < 26; i++)
        {
            v[i] = NULL;
        }
    }
};

bool stergere;
node* radacina = new node;

void add(node* nod_c, char cuv[25], int lit_c)
{
    if(lit_c == strlen(cuv))
    {
        nod_c->cnt++;
        return;
    }
    if(nod_c->v[cuv[lit_c] - 'a']==NULL)
    {
        nod_c->v[cuv[lit_c] - 'a'] = new node;
    }
    nod_c->fii++;
    add(nod_c->v[cuv[lit_c] - 'a'], cuv, lit_c + 1);
}

bool del(node* nod_c, char cuv[25], int lit_c)
{
    if(lit_c == strlen(cuv))
    {
        nod_c->cnt--;
        if(nod_c->cnt == 0 && nod_c->fii == 0)
        {
            delete nod_c;
            return 1;
        }
        return 0;
    }
    bool stergere = del(nod_c->v[cuv[lit_c]-'a'], cuv, lit_c + 1);
    if(stergere == 1)
    {
        nod_c->fii--;
        nod_c->v[cuv[lit_c]-'a'] = 0;
        if(nod_c->cnt == 0 && nod_c->fii == 0 && nod_c != radacina)
        {
            delete nod_c;
            return 1;
        } else
        {
            return 0;
        }
    }
}

void print_ap(node* nod_c, char cuv[25], int lit_c)
{
    if(lit_c == strlen(cuv))
    {
        out << nod_c->cnt << '\n';
        return;
    }
    print_ap(nod_c->v[cuv[lit_c]-'a'], cuv, lit_c + 1);
}

void common_depth(node* nod_c, char cuv[25], int lit_c, int depth)
{
    if(lit_c == strlen(cuv))
    {
        out << depth << '\n';
        return;
    }
    if(nod_c->v[cuv[lit_c] - 'a'] == NULL)
    {
        out << depth << '\n';
        return;
    }
    common_depth(nod_c->v[cuv[lit_c]-'a'], cuv, lit_c + 1, depth + 1);
}

int main()
{
    char cuv[25];
    int cerinta;
    while(in >> cerinta >> cuv)
    {
        if(cerinta == 0)
        {
            add(radacina, cuv, 0);
            continue;
        }
        if(cerinta == 1)
        {
            stergere = 0;
            del(radacina, cuv, 0);
            continue;
        }
        if(cerinta == 2)
        {
            print_ap(radacina, cuv, 0);
            continue;
        }
        if(cerinta == 3)
        {
            common_depth(radacina, cuv, 0, 0);
        }
    }
    return 0;
}