#include <fstream>
#include <cstring>

using namespace std;

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

struct trieNode
{
    int nr, nrChildren;
    trieNode *children[26], *parent;
};

trieNode *getNode(trieNode *p)
{
    trieNode *aux = new trieNode;

    aux -> nr = 0;
    aux -> nrChildren = 0;
    aux -> parent = p;
    memset(aux -> children, NULL, sizeof(aux -> children));

    return aux;
}

trieNode *root = getNode(NULL);

void Insert(trieNode *root, string key)
{
    trieNode *aux = root;

    for (int i=0; i<key.size(); i++)
    {
        int index = key[i] - 'a';

        if (!aux -> children[index])
        {
            aux -> children[index] = getNode(aux);
            aux -> nrChildren ++;
        }

        aux = aux -> children[index];
    }

    aux -> nr ++;
}

trieNode *Delete(trieNode *root, string key, int depth)
{
    if (!root)
        return NULL;

    if (depth == key.size())
    {
        root -> nr --;

        if (!root -> nr && !root -> nrChildren)
        {
            if (root -> parent)
                root -> parent -> nrChildren --;

            delete(root);
            root = NULL;
        }

        return root;
    }

    int index = key[depth] - 'a';
    root -> children[index] = Delete(root -> children[index], key, depth + 1);

    if (!root -> nrChildren && !root -> nr)
    {
        if (root -> parent)
            root -> parent -> nrChildren --;

        delete(root);
        root = NULL;
    }

    return root;
}

int nrAp(trieNode *root, string key)
{
    trieNode *aux = root;

    for (int i=0; i<key.size(); i++)
    {
        int index = key[i] - 'a';
        if (aux -> children[index])
            aux = aux -> children[index];
        else
            return 0;
    }

    return aux -> nr;
}

int maxPrefix(trieNode *root, string key)
{
    trieNode *aux = root;

    for (int i=0; i<key.size(); i++)
    {
        int index = key[i] - 'a';
        if (aux -> children[index])
            aux = aux -> children[index];
        else
            return i;
    }

    return key.size();
}

int main()
{
    char c[23];
    while (f.getline(c, 23))
    {
        if (c[0] == '0')
            Insert(root, c + 2);
        else if (c[0] == '1')
            trieNode *aux = Delete(root, c + 2, 0);
        else if (c[0] == '2')
            g << nrAp(root, c + 2) << "\n";
        else if (c[0] == '3')
            g << maxPrefix(root, c + 2) << "\n";
    }
    return 0;
}