#include <fstream>
#include <cstring>
using namespace std;

ifstream is("trie.in");
ofstream os("trie.out");

struct Trie{
    Trie()
    {
        nrfii = nrcuv = 0;
        memset(fii, 0, sizeof(fii));
    }
    int nrfii, nrcuv;
    Trie* fii[26];
};

char cuv[25];
Trie* t = new Trie;

void Insert(Trie* nod, char* s);
bool Delete(Trie* nod, char* s);
void Count(Trie* nod, char* s);
void Prefix(Trie* nod, char* s, int k);

int main()
{
    is.getline(cuv, 25, '\n');
    while ( cuv[0] >= '0' && cuv[0] <= '3' )
    {
        if ( cuv[0] == '0' ) Insert(t, cuv + 2);
        else
            if ( cuv[0] == '1' ) Delete(t, cuv + 2);
            else
                if ( cuv[0] == '2' ) Count(t, cuv + 2);
                else Prefix(t, cuv + 2, 0);
        is.getline(cuv, 25, '\n');
    }
    is.close();
    os.close();
    return 0;
}

void Insert(Trie* nod, char* s)
{
    if ( *s == '\0' )
    {
        ++nod->nrcuv;
        return;
    }
    if ( !nod->fii[*s - 'a'] )
    {
        nod->fii[*s - 'a'] = new Trie;
        ++nod->nrfii;
    }
    Insert(nod->fii[*s - 'a'], s + 1);
}

bool Delete(Trie* nod, char* s)
{
    if ( *s == '\0' )
    {
        --nod->nrcuv;
        if ( !nod->nrcuv && !nod->nrfii )
        {
            delete nod;
            return true;
        }
        return false;
    }
    if ( Delete(nod->fii[*s - 'a'], s + 1) )
    {
        nod->fii[*s - 'a'] = 0;
        --nod->nrfii;
        if ( !nod->nrcuv && !nod->nrfii && nod != t )
        {
            delete nod;
            return true;
        }
        return false;
    }
    return false;
}

void Count(Trie* nod, char* s)
{
    if ( *s == '\0' )
    {
        os << nod->nrcuv << "\n";
        return;
    }
    if ( nod->fii[*s - 'a'] )
        Count(nod->fii[*s - 'a'], s + 1);
    else
        os << "0\n";
}

void Prefix(Trie* nod, char* s, int k)
{
    if ( *s == '\0' || !nod->fii[*s - 'a'] )
    {
        os << k << "\n";
        return;
    }
    Prefix(nod->fii[*s - 'a'], s + 1, k + 1);
}