#include <bits/stdc++.h>

using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

const int N_MAX = 26;

string s;

struct Node {
    int strEnd;
    int cnt;
    Node* next[N_MAX];
    Node() {
        strEnd = 0;
        cnt = 0;
        for (int i = 0; i < N_MAX; ++i) {
            next[i] = NULL;
        }
    }
};

Node* root;
void push() {
    Node* currNode = root;
    for (int i = 0; i < s.size(); ++i) {
        if (currNode -> next[s[i] - 'a'] == NULL) {
            currNode -> next[s[i] - 'a'] = new Node;
        }
        currNode = currNode -> next[s[i] - 'a'];
        currNode -> cnt += 1;
    }
    currNode -> strEnd += 1;
}

void pop(int p, Node* currNode) {
    if (p == s.size()) {
        currNode -> strEnd -= 1;
        return;
    }
    pop(p + 1, currNode -> next[s[p] - 'a']);
    currNode -> next[s[p] - 'a'] -> cnt -= 1;
    if (currNode -> next[s[p] - 'a'] -> cnt == NULL) {
        delete currNode -> next[s[p] - 'a'];
        currNode -> next[s[p] - 'a'] = NULL;
    }
}

int getFreq() {
    Node* currNode = root;
    for (int i = 0; i < s.size(); ++i) {
        if (currNode -> next[s[i] - 'a'] == NULL) {
            return false;
        }
        currNode = currNode -> next[s[i] - 'a'];
    }
    return currNode -> strEnd;
}

int getPref() {
    Node* currNode = root;
    for (int i = 0; i < s.size(); ++i) {
        if (currNode -> next[s[i] - 'a'] == NULL) {
            return i;
        }
        currNode = currNode -> next[s[i] - 'a'];
    }
    return s.size();
}

int main() {
    root = new Node;
    int op;
    while (fin >> op >> s) {
        if (op == 0) {
            push();
        } else if (op == 1) {
            pop(0, root);
        } else if (op == 2) {
            fout << getFreq() << "\n";
        } else if (op == 3) {
            fout << getPref() << "\n";
        }
    }
    return 0;
}