#include <iostream>
#include <stdio.h>
#include <fstream>
using namespace std;

#define fiu (*s -'a')

ofstream out("trie.out");

class Trie {
    int aparitii;
    int nr_fii;
    Trie *litere[26];
public:

    Trie () {
        aparitii = nr_fii = 0;
        //memset(fii, NULL, sizeof(fii));
       int i;
       for (i = 0 ; i < 26; i++)
            litere[i] = NULL;
    }

    void insert (char *s) {
        if (*s == '\n' || *s == '\0') {
            aparitii++;
            return;
        }
        if (litere[fiu] == NULL) {
            litere[fiu] = new Trie;
            nr_fii++;
        }
        litere[fiu]->insert(s + 1);
    }

    void del (char *s, int ok) {
        if (*s == '\n' || *s == '\0') {
            aparitii--;
            if (ok == 0) {
                delete this;
            }
            return;
        }
        if (litere[fiu] != NULL) {
            if (*(s + 1) == '\n' || *(s + 1) == '\0') {
                if (litere[fiu]->nr_fii == 0 && litere[fiu]->aparitii - 1 == 0) {
                    Trie *parinte = litere[fiu];
                    litere[fiu] = NULL;
                    ok = 0;
                    parinte->del(s + 1, ok);
                }
                else
                    litere[fiu]->del(s + 1, ok);
            }
            else
                litere[fiu]->del(s + 1, ok);
        }
    }

    void nr_aparitii (char *s) {
        if (*s == '\n' || *s == '\0') {
            out << aparitii <<"\n";
            return;
        }
        if (litere[fiu] == NULL) {
            out << "0\n";
            return;
        }
        litere[fiu]->nr_aparitii(s+1);
    }

    void prefix (char *s, int contor) {
        if (*s == '\n' || *s == '\0') {
            out << contor << "\n";
            return;
        }
        if (litere[fiu] != NULL) {
            contor++;
            litere[fiu]->prefix(s + 1, contor);
        }
        else {
            out << contor << "\n";
            return;
        }
    }

    bool is (char *s) {
        if (*s == '\n' || *s == '\0') {
            if (aparitii != 0)
                return true;
            else
                return false;
        }
        if (litere[fiu] == NULL)
            return false;
        return litere[fiu]->is(s + 1);
    }
};

int main() {
    ifstream in;
    in.open("trie.in");
    Trie *trie = new Trie;
    char cuvant[25];
    while (in.getline(cuvant,25)) {
        if (cuvant[0] == '0')
            trie->insert(cuvant + 2);
        else if (cuvant[0] == '1')
            trie->del(cuvant + 2, 1);
        else if (cuvant[0] == '2')
            trie->nr_aparitii(cuvant + 2);
        else if (cuvant[0] == '3')
            trie->prefix(cuvant + 2,0);
    }
    return 0;
}