#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;

struct nod{
    int n;
    nod* copacel['z'-'a'+1];
    nod(){
        n=0;
        for(int i=0;i<'z'-'a'+1;i++) copacel[i]=0;
    }
    bool prefix(){
        for(int i=0;i<'z'-'a'+1;i++) if(copacel[i]) return true;
        return false;
    }
};
nod trie;

void adauga(string w);
void sterge(string w);
int nr_cuvinte(string w);
int prefix(string w);

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

    while(true){
        string s;
        int i;
        in>>i>>s;
        if(in.good()){
            cout<<i<<"  "<<s<<endl;
            switch(i){
                case 0:adauga(s);break;
                case 1:sterge(s);break;
                case 2:out<<nr_cuvinte(s)<<"\n";break;
                case 3:out<<prefix(s)<<"\n";break;
            }
        }else{return 0;}
    }
}
void adauga(string w){
    nod* pointer=&trie;
    for(int i=0;i<w.length();i++){
        if(!pointer->copacel[w[i]-'a']){
            pointer->copacel[w[i]-'a']=new nod;
        }
        pointer=pointer->copacel[w[i]-'a'];
    }
    pointer->n++;
}
void sterge(string w){
    nod* pointer=&trie;
    vector<nod*> v;v.push_back(&trie);
    for(int i=0;i<w.length();i++){
        pointer=pointer->copacel[w[i]-'a'];
        v.push_back(pointer);
    }
    pointer->n--;
    for(int i=v.size()-1;i>0;i--){
        if(v[i]->n==0 and v[i]->prefix()==false){
            delete v[i-1]->copacel[w[i-1]-'a'];
            v[i-1]->copacel[w[i-1]-'a']=0;
        }
    }
}
int nr_cuvinte(string w){
    nod* pointer=&trie;
    for(int i=0;i<w.length();i++){
        if(!pointer->copacel[w[i]-'a']) return 0;
        pointer=pointer->copacel[w[i]-'a'];
    }
    return pointer->n;
}
int prefix(string w){
    nod* pointer=&trie;
    int p=0;
    for(int i=0;i<w.length();i++){
        p=i;
        if(!pointer->copacel[w[i]-'a']) break;
        pointer=pointer->copacel[w[i]-'a'];
    }
    return p;
}