#include<stdio.h>
#include<cstdlib>
#include<string.h>

using namespace std;

struct Trie{
    int val, cnt;
    Trie *parent;
    Trie* fii[26];

    Trie(){
        val = 0;
        cnt = 0;
        parent = NULL;
        for (int i = 0; i < 26; i++){
            fii[i] = NULL;
        }
    }
};

Trie *T = new Trie();

void adaugare(char c[20]){
    int l = strlen(c);
   // printf("aici");
    Trie *Nod = T;
    for(int i = 0; i < l; i++){
        int j = c[i] - 'a';
        //printf("j = %d l = %d\n", j, l);
        if (Nod->fii[j] == NULL){
            Trie *aux = new Trie();
            if (i == l-1){
                aux->val = 1;
            }else{
                aux->val = 0;
            }
            aux->parent = Nod;
            Nod->fii[j] = aux;
            Nod->cnt++;
         //   printf("cnt = %d val = %d\n", Nod->cnt, Nod->fii[j]->val);
        }else{
            if (i == l-1){
                Nod->fii[j]->val++;
           //     printf("val = %d\n", Nod->fii[j]->val);
            }
        }
        Nod = Nod->fii[j];
    }
}

void stergere(char c[20]){
    int l = strlen(c);
    Trie *Nod = T;
    //Trie *Par = NULL;
    for (int i = 0; i < l; i++){
        int j = c[i] - 'a';
        if (Nod->fii[j] == NULL)
            break;
        Nod = Nod->fii[j];
    }
  //  printf("NULLLLLL\n");
    for(int i = l-1; i >= 0; i--){
        Trie *aux = new Trie;
        if (Nod->cnt > 0){
            if (Nod->val > 0)
                Nod->val--;
                break;
        }else{
            if (Nod->val <= 1){
                aux = Nod;
                Nod = Nod->parent;
                Nod->fii[c[i] - 'a'] = NULL;
                Nod->cnt--;
                delete aux;
            }else{
               // printf ("val = %d\n", Nod->val);
                Nod->val--;
                break;
            }

        }
    }
}

int nraparitii(char c[20]){
    int l = strlen(c);
    Trie *aux = T;
    for (int i = 0; i < l; i++){
        int j = c[i] - 'a';
        if (aux -> fii[j] == NULL) {
            return 0;
        }
       // printf("i = %d\n", i);
        aux = aux->fii[j];
    }
    return aux->val;
}

int prefix(char c[20]){
    int p = 0, l = strlen(c);
    Trie *aux = T;
    for (int i = 0; i < l && aux != NULL; i++){
        int j = c[i] - 'a';

        if (aux->fii[j] != NULL){
            p = i + 1;
           //printf("*j = %d, cnt = %d p = %d\n", j,aux->cnt, p);
        }/*else if (aux->fii[j] == NULL){
            p = i;
            printf("j = %d, cnt = %d, p = %d\n", j, aux->cnt, p);
        }*/
        aux = aux->fii[j];
    }

    return p;
}

int main(){
    int q;
    char s[20];
    //printf("aici");
    freopen("trie.in", "r", stdin);
    freopen("trie.out", "w", stdout);
    //int x = 3;
    //printf("%d", x);
    while(!feof(stdin)){
        if(scanf("%d %s", &q, s) == EOF)
            break;
       // printf("********Q = %d\n", q);
        if(q == 0)
            adaugare(s);
        if(q == 1)
            stergere(s);
        if(q == 2)
           printf("%d\n", nraparitii(s));
        if(q == 3)
           printf("%d\n", prefix(s));
    }
    return 0;
}