#include <iostream>
#include <fstream>

using namespace std;

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

struct node{
    int data;
    node *next['z'-'a'+1];
};
node* create()
{
    node *n=new node;
    for(int i=0;i<26;i++)
    {
        n->next[i]=nullptr;
    }
    n->data=0;
    return n;
}

void trie_insert(node *gy,char *word)
{
    char ch= *word;
    if(ch=='\0')
        gy->data++;
    else{
        int index=ch-'a';
        if(gy->next[index]==nullptr)
        {
            gy->next[index]=create();
        }
        trie_insert(gy->next[index],word +1);
    }
}

bool trie_arva(node *gy)
{
    if(gy->data!=0)return false;

    bool van=false;
    for(int i=0;i<26;i++)
        if(gy->next[i]!=nullptr)
            van=true;
    return !van;

}

bool trie_delete(node *gy,char *word)
{
    char ch= *word;
    if(ch=='\0'){
        if(gy->data>0)
            gy->data--;
        if(trie_arva(gy)){
            delete gy;
            return true;
        }
        return false;
    }
    else{
        int index=ch-'a';
        if(gy->next[index]==nullptr)
        {
            return false;
        }
        if(trie_delete(gy->next[index],word +1))
        {
            gy->next[index]=nullptr;
            if(trie_arva(gy)){
                delete gy;
                return true;
            }

        }
        return false;
    }


}

int trie_search(node *gy,char *word)
{
    char ch= *word;
    if(ch=='\0'){
            return gy->data;
    }
    else{
        int index=ch-'a';
        if(gy->next[index]==nullptr)
        {
            return 0;
        }
        return trie_search(gy->next[index],word +1);
    }
}

char *trie_prefix_length_helper(node *gy,char *word)
{
    char ch= *word;
    if(ch=='\0'){
            return word;
    }
    else{
        int index=ch-'a';
        if(gy->next[index]==nullptr)
        {
            return word;
        }
        return trie_prefix_length_helper(gy->next[index],word +1);
    }
}

int trie_prefix_length(node *gy,char *word)
{
    return (trie_prefix_length_helper(gy,word)-word);
}
int main()
{
    int n;
    char word[21];
    node *gy=create();

    while(be>>n>>word)
    {
        switch(n){
        case 0:
            trie_insert(gy,word);
            break;
        case 1:
            if(trie_delete(gy,word))
                gy=create();
            break;
        case 2:
            ki<<trie_search(gy,word)<<'\n';
            break;
        case 3:
            ki<<trie_prefix_length(gy,word)<<'\n';
            break;

        }
    }
    return 0;
}