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

using namespace std;

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

struct trie
{
    int cnt, nrs;
    trie *fiu[27];

    trie()  ///constructorul structurii. Se va apela de fiecare data cand cream un nod de tipul trie
    {
        cnt = nrs = 0;
        memset(fiu, 0, sizeof(fiu));
    }
};

trie *root = new trie();

void add_word(trie *nod, char *s)
{
    if(*s==NULL)  ///Daca am ajuns la finalul cuvantului
    {
        nod->cnt++;
        return;
    }
    int delta = *s - 'a'; ///Aflam care e urmatorul nod in care vom merge
    if(nod->fiu[delta] == NULL)
    {
        nod->fiu[delta] = new trie();
        nod->nrs++;
    }

    add_word(nod->fiu[delta], s+1);
}

int find_word(trie *nod, char *s)
{
    if(*s==NULL)
        return nod->cnt;

    int delta = *s - 'a';

    if(nod->fiu[delta]==NULL)
        return 0;

    return find_word(nod->fiu[delta], s+1);
}

bool Delete(trie *nod, char *s)
{
    if(*s == NULL){
        nod->cnt--;
        if(nod->cnt == 0 && nod->nrs == 0 && nod!=root){
            delete nod;
            return 1;
        }
        return 0;
    }

    int delta = *s-'a';

    if(Delete(nod->fiu[delta], s+1)){
        nod->nrs--;
        nod->fiu[delta]=0;
        if(nod->cnt == 0 && nod->nrs == 0 && nod!=root){
            delete nod;
            return 1;
        }
    }

    return 0;
}

int find_longest_prefix(trie *nod, char *s)
{
    if(*s == NULL)
        return 0;

    int delta = *s - 'a';

    if(nod->fiu[delta] == NULL)
        return 0;

    return  1 + find_longest_prefix(nod->fiu[delta], s+1);


}


int main()
{

    int operationType;
    char cuvant[25];

    while(f >> operationType >> cuvant)
    {

        switch(operationType)
        {
        case 0:
            add_word(root, cuvant);
            break;
        case 1:
            Delete(root, cuvant);
            break;
        case 2:
            g << find_word(root, cuvant) << "\n";
            break;
        case 3:
            g << find_longest_prefix(root, cuvant) << "\n";
            break;
        }

    }
    return 0;
}