#include <fstream>
#include <cstring>

using namespace std;

char rand[50];

struct trie {
    int nr;
    trie *fiu[26];
    int fii;
    trie() {
        memset(fiu,0,sizeof(fiu));
        fii=nr=0;
    }
} *T = new trie;

void update(trie *nod, char *s) {
    if(*s == 0) {
        nod->nr++;
        return;
    }
    if(nod->fiu[*s - 'a']==0) {
        nod->fiu[*s - 'a']=new trie;
        nod->fii++;
    }
    update(nod->fiu[*s-'a'],s+1);
}

bool Delete(trie *nod, char *s) {
    if(*s == 0)
        nod->nr--;
    else
    if(Delete(nod->fiu[*s-'a'],s+1)) {
        nod->fiu[*s-'a']=0;
        nod->fii--;
    }
    if(nod->nr==0 && nod->fii==0 && nod!=T) {
        delete nod;
        return 1;
    }
    return 0;
}

int query(trie *nod, char *s) {
    if(*s == 0)
        return nod->nr;
    if(nod->fiu[*s-'a'])
        return query(nod->fiu[*s-'a'],s+1);
    return 0;
}

int prefix(trie *nod, char *s, int k) {
    if(*s==0 || nod->fiu[*s-'a']==0)
        return k;
    return prefix(nod->fiu[*s-'a'],s+1,k+1);
}

int main() {
    ifstream f("trie.in");
    ofstream g("trie.out");
    while(f.get(rand,40)) {
        if(rand[0]=='0') {
            update(T,rand+2);
        }
        else
        if(rand[0]=='1') {
            Delete(T,rand+2);
        }
        else
        if(rand[0]=='2') {
            g<<query(T,rand+2)<<"\n";
        }
        else
        if(rand[0]=='3') {
            g<<prefix(T,rand+2,0)<<"\n";
        }
        f.get();
    }
    return 0;
}