#include <fstream>
using namespace std;
ifstream cin("trie.in");
ofstream cout("trie.out");

int nextnodliber=1,max1;
string s;
int cnt[2100001],cntp[2100001],nxt[2100001][26];

void build_trie(int nod,int poz){
    cntp[nod]++;
    if(poz==(int)s.size()){cnt[nod]++;return;}
    if(!nxt[nod][s[poz]-'a'])nxt[nod][s[poz]-'a']=nextnodliber++;
    build_trie(nxt[nod][s[poz]-'a'],poz+1);
}

void scad_trie(int nod,int poz){
    cntp[nod]--;
    if(poz==(int)s.size()){cnt[nod]--;return;}
    int c=nxt[nod][s[poz]-'a'];
    if(!c)return;
    scad_trie(c,poz+1);
}

int nr_trie(int nod,int poz){
    if(poz==(int)s.size())return cnt[nod];
    int c=nxt[nod][s[poz]-'a'];
    if(!c)return 0;
    return nr_trie(c,poz+1);
}

void max_pref(int nod,int poz){
    if(cntp[nod]>0)max1=poz;
    if(poz==(int)s.size())return;
    int c=nxt[nod][s[poz]-'a'];
    if(!c)return;
    max_pref(c,poz+1);
}

int main(){
    int cer;
    while(cin>>cer){
        cin>>s;
        max1=0;
        if(cer==0)build_trie(0,0);
        else if(cer==1)scad_trie(0,0);
        else if(cer==2)cout<<nr_trie(0,0)<<"\n";
        else{max_pref(0,0);cout<<max1<<"\n";}
    }
    return 0;
}