#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define NL 26
#define LC 20

typedef struct nod
{
    struct nod * fii[NL];
    int nr_ap;
} nod;

nod* init(nod *p)
{
    p = (nod*)malloc(sizeof(nod));
    p->nr_ap = 0;
    for (int i = 0; i < NL; i++)
    {
        p->fii[i] = NULL;
    }
    return p;
}

nod* adauga(nod *p, char *s)
{
    if (p == NULL)
    {
        p = init(p);
    }
    if (s[0] == '\0')
    {
        p->nr_ap++;
    }
    else
    {
        p->fii[s[0]-'a'] = adauga(p->fii[s[0]-'a'], s + 1);
    }
    return p;
}

int nr_aparitii(nod *p, char *s)
{
    if (s[0] == '\0')
    {
        return p->nr_ap;
    }
    if (p->fii[s[0]-'a'] != NULL)
    {
        return nr_aparitii(p->fii[s[0]-'a'], s + 1);
    }
    return 0;
}

bool este_frunza(nod *p)
{
    for (int i = 0; i < NL; i++)
    {
        if (p->fii[i] != NULL)
        {
            return false;
        }
    }
    return true;
}

nod* sterge(nod *p, char *s)
{
    if (s[0] == '\0')
    {
        p->nr_ap--;
    }
    else
    {
        p->fii[s[0]-'a'] = sterge(p->fii[s[0]-'a'], s + 1);
    }
    if (p->nr_ap == 0 && este_frunza(p))
    {
        free(p);
        p = NULL;
    }
    return p;
}

int lungime_prefix(nod *p, char *s)
{
    if (p == NULL || s[0] == '\0')
    {
        return 0;
    }
    if (p->fii[s[0]-'a'] == NULL)
    {
        return 0;
    }
    return 1 + lungime_prefix(p->fii[s[0]-'a'], s + 1);
}

int main()
{
    FILE *in, *out;
    in = fopen("trie.in", "r");
    out = fopen("trie.out", "w");
    int tip;
    char s[LC+1];
    nod *r = NULL;
    while (fscanf(in, "%d %s", &tip, s) != EOF)
    {
        if (tip == 0)
        {
            r = adauga(r, s);
        }
        if (tip == 1)
        {
            r = sterge(r, s);
        }
        if (tip == 2)
        {
            fprintf(out, "%d\n", nr_aparitii(r, s));
        }
        if (tip == 3)
        {
            fprintf(out, "%d\n", lungime_prefix(r, s));
        }
    }
    return 0;
}