#include <iostream>
#include <fstream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("trie.in");
ofstream fout("trie.out");
int op, n, nodeCount = 1;
char cuv[22];
vector <vector <int> > trie;
vector <char> trieLetter;
vector <int> trieCount;
void afis() {
    for(int i = 0; i < trie.size(); i++) {
        if(trie[i].size())
        fout<<i<<": ";
        for(int j = 0; j < trie[i].size(); j++) {
            fout<<trie[i][j]<<"(";
            fout<<trieLetter[trie[i][j]]<<", ";
            fout<<trieCount[trie[i][j]];
            fout<<") ";
        }
        if(trie[i].size())
        fout<<'\n';
    }
    fout<<'\n';
    fout<<'\n';
}

void adauga() {
    int poz = 0, R = 0, k = 0;
    while (k < trie[R].size() && poz <= n) {
        if(trieLetter[trie[R][k]] == cuv[poz]) {
            R = trie[R][k];
            k = 0;
            poz++;
        } else {
            k++;
        }
    }
    while (poz <= n) {
        trieCount.resize(nodeCount + 1);
        trieLetter.resize(nodeCount + 1);
        trie.resize(R + 1);
        /*
        if(nodeCount + 21 >= trieCount.size()) {
            trieCount.resize(nodeCount + 22);
            trieLetter.resize(nodeCount + 22);
        }
        if(R + 21>= trie.size()) {
            trie.resize(R + 22);
        }
        */
        //cout<<trie.size()<<' '<<R<<' '<<nodeCount<<'\n';
        trie[R].push_back(nodeCount);
        R = *(trie[R].end() - 1);
        nodeCount++;
        trieLetter[nodeCount - 1] = cuv[poz];
        poz++;
    }
    trieCount[R]++;
    //afis();
}

void sterge() {
    stack <int> st;
    int R = 0, k = 0, poz = 0;
    st.push(R);
    while (k < trie[R].size() && poz <= n) {
        if (trieLetter[trie[R][k]] == cuv[poz]) {
            R = trie[R][k];
            st.push(R);
            k = 0;
            poz++;
        } else {
            k++;
        }
    }
    int aux = st.top();
    st.pop();
    k = st.top();
    while(!st.empty() && trie[k].size() > 1) {
        // diferit de 0?
        k = st.top();
        st.pop();
        for (int i = 0; i < trie[k].size(); i++) {
            if (trie[k][i] == aux) {
                trie[k].erase(trie[k].begin() + i);
            }
        }
        aux = k;
    }
    trieCount[R]--;
}

void nrAparitii() {
    int R = 0, k = 0, poz = 0;
    while (k < trie[R].size() && poz <= n) {
        if (trieLetter[trie[R][k]] == cuv[poz]) {
            R = trie[R][k];
            k = 0;
            poz++;
        } else {
            k++;
        }
    }
    fout<<trieCount[R]<<'\n';
}

void lungimePrefix() {
    int R = 0, k = 0, poz = 0;
    while (k < trie[R].size() && poz <= n) {
        if (trieLetter[trie[R][k]] == cuv[poz]) {
            R = trie[R][k];
            k = 0;
            poz++;
        } else {
            k++;
        }
    }
    fout<<poz<<'\n';
}
/*
void sterge() {

}
void nrAparitii() {

}
void lungimePrefix() {

}
*/
int main()
{
    trie.resize(1);
    while(fin>>op>>cuv) {
        n = strlen(cuv) - 1;
        if (op == 0) {
            adauga();
        } else if (op == 1) {
            sterge();
        } else if (op == 2) {
            nrAparitii();
        } else if (op == 3) {
            lungimePrefix();
        }
    }
    //afis();
    fin.close();
    fout.close();
    return 0;
}

/*
0 lat
0 mare
0 lac
2 la
0 mare
1 lat
0 ma
0 lung
3 latitudine
0 mari
2 mare
0 lat
0 mic
3 latime
2 lac
3 mire
*/