#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Node
{
    Node(int x)
    {
        nr = x;
        prev = nullptr;
        for(int i = 0; i < 26; i++)
            next[i] = nullptr;
    }
    Node* prev;
    Node* next[28];
    
    int nr;
};

inline string cut_last(string word)
{
    word.pop_back();
    return word;
}

void insert_dfs(Node* node, string word)
{
    if(word.size() == 0)
    {
        (node->nr)++;
        return;
    }
    if(!((node->next)[word.back() - 'a']))
        (node->next)[word.back() - 'a'] = new Node(0);
    insert_dfs((node->next)[word.back() - 'a'], cut_last(word));
}

void delete_dfs(Node* node, string word)
{
    if(word.size() == 0)
    {
        (node->nr)--;
        return;
    }

    if(!((node->next)[word.back() - 'a']))
        return;
    delete_dfs((node->next)[word.back() - 'a'], cut_last(word));

    if((node->next)[word.back() - 'a']->nr == 0)
    {
        bool ok = 1;
        for(int i = 0; i < 26; i++)
            if(((node->next)[word.back() - 'a']->next)[i])
            {
                ok = 0;
                break;
            }
        if(ok)
            (node->next)[word.back() - 'a'] = nullptr;
    }
}

int count_dfs(Node* node, string word)
{
    if(word.size() == 0)
        return node->nr;
    
    if(!((node->next)[word.back() - 'a']))
        return 0;
    
    return count_dfs((node->next)[word.back() - 'a'], cut_last(word));
}

int prefix_length_dfs(Node* node, string word, int k)
{
    if(word.size() == 0)
        return k;

    if(!((node->next)[word.back() - 'a']))
        return k;
    
    return prefix_length_dfs((node->next)[word.back() - 'a'], cut_last(word), k + 1);
}

int main()
{
    ifstream f("trie.in");
    ofstream g("trie.out");
    string s;

    Node* root = new Node(0);

    while(getline(f, s))
    {
        int x = s[0] - '0';
        string word(s, 2);

        reverse(word.begin(), word.end());
        if(x == 0)
            insert_dfs(root, word);
        else if(x == 1)
            delete_dfs(root, word);
        else if(x == 2)
            g << count_dfs(root, word) << '\n';
        else if(x == 3)
            g << prefix_length_dfs(root, word, 0) << '\n';
    }

    return 0;
}