#include <bits/stdc++.h>

using namespace std;

const int sigma = 'z' - 'a' + 1;

struct Trie
{
    int val , sons;
    Trie *son[sigma];

    Trie()
    {
        val = 0; sons = 0;
        for (int i = 0 ; i < sigma; ++i) son[i] = NULL;
    }
};

int tip;
string sir;

Trie *root;

void in(Trie *nod , int p)
{
    if (p == sir.size())
    {
        nod -> val++;
        return;
    }

    int ind = sir[p] - 'a';
    if (nod -> son[ind] == NULL)
        nod -> son[ind] = new Trie, nod -> sons++;
    in(nod -> son[ind] , p + 1);
}

void out(Trie *nod , int p)
{
    if (p == sir.size())
    {
        nod -> val--;
        return;
    }

    int ind = sir[p] - 'a';
    out(nod -> son[ind] , p + 1);
    if (nod -> son[ind] -> val == 0 && nod -> son[ind] -> sons == 0)
        nod -> son[ind] = NULL, nod -> sons--;
}

int nr(Trie *nod , int p)
{
    if (p == sir.size())
        return nod -> val;

    int ind = sir[p] - 'a';
    if (nod -> son[ind] == NULL) return 0;
    return nr(nod -> son[ind] , p + 1);
}

int prefix(Trie *nod , int p)
{
    int ind = sir[p] - 'a';

    if (p == sir.size() || nod -> son[ind] == NULL)
        return p;

    return prefix(nod -> son[ind] , p + 1);
}


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

    root = new Trie;

    while (fin >> tip >> sir)
    {
        if (!tip) in(root , 0);
        if (tip == 1) out(root , 0);
        if (tip == 2) fout << nr(root , 0) << '\n';
        if (tip == 3) fout << prefix(root , 0) << '\n';

    }

    return 0;
}