#include <fstream>
#include <vector>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

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

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

using VI = vector<int>;
using VVI = vector<VI>;

char s[22];

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

int main()
{
    while ( is.getline(s, 22, '\n') )
    {
        switch ( s[0] )
        {
            case '0': { Insert(t, s + 2); break; }
            case '1': { Delete(t, s + 2); break; }
            case '2': { os << Count(t, s + 2) << "\n"; break; }
            case '3': { Prefix(t, s + 2, 0); break; }
        }
    }
    is.close();
    os.close();
    return 0;
}

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);
}

int Count(Trie *nod, char *s)
{
    if ( *s == '\0' )
        return nod->nrcuv;
    if ( nod->fii[*s - 'a'] )
        return Count(nod->fii[*s - 'a'], s + 1);
    return 0;
}

void Insert(Trie *nod, char *s)
{
    if ( *s == '\0' )
    {
        ++nod->nrcuv;
        return;
    }
    if ( !nod->fii[*s - 'a'] )
    {
        ++nod->nrfii;
        nod->fii[*s - 'a'] = new Trie;
    }
    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->nrfii;
        nod->fii[*s - 'a'] = 0;
        delete nod->fii[*s - 'a'];
        if ( !nod->nrcuv && !nod->nrfii && nod != t )
        {
            delete nod;
            return true;
        }
    }
    return false;
}