#include <bits/stdc++.h>

using namespace std;

#define ST_DIO 0
#if ST_DIO
    #define fin cin
    #define fout cout
#else
    ifstream fin("trie.in");
    ofstream fout("trie.out");
#endif  // ST_DIO

struct NodTrie {
    NodTrie* fii[26];
    int nrFii, nrCuv;
};
NodTrie* radTrie;

static inline NodTrie* NodNou() {
    NodTrie* nod = new NodTrie;
    for(int i = 0; i < 26; i++) nod->fii[i] = NULL;
    nod->nrCuv = 0;
    nod->nrFii = 0;
    return nod;
}

static inline void StergeNod(NodTrie* nod) {
    for(int i = 0; i < 26; i++) {
        if(NULL != nod->fii[i]) StergeNod(nod->fii[i]);
    }
    delete nod;
}

static inline void AdaugaInTrie(NodTrie* nod, const string& s, int poz = 0) {
    if(s.size() == poz) {
        nod->nrCuv++;
        return;
    }
    char lit = s[poz] - 'a';
    if(NULL == nod->fii[lit]) {
        nod->fii[lit] = NodNou();
        nod->nrFii++;
    }
    AdaugaInTrie(nod->fii[lit], s, 1 + poz);
}

static inline bool StergeInTrie(NodTrie* nod, const string& s, int poz = 0) {
    if(s.size() == poz) {
        nod->nrCuv--;
        return 0 == nod->nrCuv && 0 == nod->nrFii;
    }
    char lit = s[poz] - 'a';
    if(NULL == nod->fii[lit]) return false;

    if(StergeInTrie(nod->fii[lit], s, 1 + poz)) {
        StergeNod(nod->fii[lit]);
        nod->fii[lit] = NULL;
        nod->nrFii--;

        return 0 == nod->nrFii;
    }
    return false;
}

static inline int CautaFrecventa(NodTrie* nod, const string& s, int poz = 0) {
    if(s.size() == poz) return nod->nrCuv;
    char lit = s[poz] - 'a';
    if(NULL == nod->fii[lit]) return 0;
    return CautaFrecventa(nod->fii[lit], s, 1 + poz);
}

static inline int CautaPrefMax(NodTrie* nod, const string& s, int poz = 0) {
    if(s.size() == poz) return poz;
    char lit = s[poz] - 'a';
    if(NULL == nod->fii[lit]) return poz;
    return CautaPrefMax(nod->fii[lit], s, 1 + poz);
}

int main() {
    if(ST_DIO) ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    radTrie = NodNou();

    int op;
    string s;
    while(fin >> op) {
        fin >> s;
        switch(op) {
            case 0: AdaugaInTrie(radTrie, s); break;
            case 1: StergeInTrie(radTrie, s); break;
            case 2: fout << CautaFrecventa(radTrie, s) << '\n'; break;
            default: fout << CautaPrefMax(radTrie, s) << '\n'; break;
        }
    }

    return 0;
}