#include<stdio.h>
#include<cstring>
#include<unistd.h>

struct nod
{
    nod *v[26];
    int capat;
    int nrf;
    nod ()
    {
        capat = nrf = 0;
        for(int i = 0; i < 26; i++) {
            v[i] = NULL;
        }
    }
};

FILE *in, *out;

void add(char* s, nod* start)
{
    int i = 0;
    while(s[i] != 0) {
        if(start->v[s[i] - 'a'] == NULL) {
            (start->v[s[i] - 'a']) = new nod;
            start->nrf++;
        }
        start = start->v[s[i] - 'a'];
        i++;
    }
    (start->capat)++;
}

int del(char *s, nod *start)
{
    if (start == NULL) {
        return 0;
    }
    if(s[0] == 0) {
        if(start->capat > 1) {
            start->capat--;
            return 0;
        } else {
            delete start;
            return 1;
        }
    } else {
        int dai = del(s + 1, start->v[s[0] - 'a']);
        if(dai == 0) {
            return 0;
        } else {
            start->v[s[0] - 'a'] = NULL;
            start->nrf--;
            if(start->nrf == 0 && start->capat == 0) {
                delete start;
                return 1;
            } else {
                return 0;
            }
        }
    }
}

int nrapa(char* s, nod* start)
{
    int i = 0;
    while(s[i] != 0 && start->v[s[i] - 'a'] != NULL) {
        start = start->v[s[i] -'a'];
        i++;
    }
    if(s[i] == 0) {
        return start->capat;
    } else {
        return 0;
    }
}


int prefcom(char* s, nod* start)
{
    int i = 0;
    while(s[i] != 0 && start->v[s[i] - 'a'] != NULL) {
        start = start->v[s[i] -'a'];
        i++;
    }

    return i;
}
int main ()
{
    in = fopen("trie.in", "r");
    out = fopen("trie.out", "w");

    nod *trie, *ctrie;
    trie = new nod;
    ctrie = trie;
    int x;
    int op;
    char *cuv, c;
    cuv = new char [25];
    while(fscanf(in, "%d %s\n", &op, cuv) == 2) {
        //fprintf(stdout, "%d %s\n", op, cuv);
        //c = fgetc(in);
        //trie = ctrie;
        switch(op)
        {
            case 0:
                //write(2, "GYA\n", 4);
                add(cuv, trie);
                //del(cuv, trie);
                break;
            case 1:
                del(cuv, trie);
                break;
            case 2:
                x = nrapa(cuv, trie);
                fprintf(out, "%d\n", x);
                break;
            case 3:
                x = prefcom(cuv, trie);
                fprintf(out, "%d\n", x);
                break;
            default:
                break;
        }
        int i = 0;
        while(cuv[i] != 0) {
            cuv[i] = 0;
            ++i;
        }
    }

    fclose(in);
    fclose(out);

    return 0;
}