#include <iostream>
#include <fstream>
#include <string>
using namespace std;


string word;

ifstream f ("trie.in");

struct trieNode {
    int f;
    trieNode *fiu[30];
    trieNode() {
        f = 0;
        for (int i = 0; i < 30; i ++) {
            fiu[i] = 0;
        }
    }
};

trieNode *r;

void insertTrie(trieNode *r, int poz) {
    if (poz == word.size()) {
        r->f++;
        return;
    }
    int ind = word[poz] - 'a';
    if (r->fiu[ind] == 0) {
        r->fiu[ind] = new trieNode();
    }
    insertTrie(r->fiu[ind], poz + 1);
}

int getNrSons(trieNode *r) {
    int nr = 0;
    for (int i = 0 ; i < 30 ; i++)
    if (r->fiu[i] != 0) {
        nr ++;
    }
    return nr;
}

bool deletenode = false;
void deleteTrie(trieNode *r, int poz ) {
    if (poz == word.size()) {
        r->f--;
        if (r->f == 0 && getNrSons(r) == 0) {
            deletenode = true;
        }
        return;
    }
    int ind = word[poz] - 'a';
    deleteTrie(r->fiu[ind], poz+1);
    if ( deletenode == true ) {
        r->fiu[ind] = 0;
        if (getNrSons(r) > 0 || r->f >0) {
            deletenode = false;
        }
    }
}

int getFrecv(trieNode *r, int poz) {
    if (poz == word.size()) {
        return r->f;
    }
    int ind = word[poz] - 'a';
    if (r->fiu[ind]!=0){
        return getFrecv(r->fiu[ind], poz + 1);
    }
    return 0;
}

int getPrefix(trieNode *r, int poz) {
    if (poz == word.size()) {
        return poz;
    }
    int ind = word[poz] - 'a';
    if (r->fiu[ind] == 0) {
        return poz;
    }
    return getPrefix(r->fiu[ind], poz + 1);
}

void solve() {
    ofstream g("trie.out");
    r = new trieNode();
    int op;
    while (f >> op) {
        f >> word;
        if (op == 0) {
            insertTrie(r, 0);
        }
        if ( op == 1 ){
            deleteTrie(r, 0);
        }
        if (op == 2) {
            g << getFrecv(r, 0) <<'\n';
        }
        if (op == 3) {
            g << getPrefix(r, 0) << '\n';
        }
    }
    f.close();
    g.close();
}

int main() {
    solve();
    return 0;
}