#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 (Trie *&parinte, char *s) {
        if (*s == '\n' || *s == '\0') {
            aparitii--;
            if (aparitii == 0 && nr_fii == 0) {
                parinte = NULL;
            }
            return;
        }
        if (litere[fiu] != NULL) {
            litere[fiu]->del(litere[fiu],s + 1);
        }
    }

    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;
    int tipOp;
    char cuvant[21];
    while (!in.eof()) {
        in >> tipOp;
        in >> cuvant;
        if (tipOp == 0)
            trie->insert(cuvant);
        else if (tipOp == 1)
            trie->del(trie, cuvant);
        else if (tipOp == 2)
            trie->nr_aparitii(cuvant);
        else if (tipOp == 3)
            trie->prefix(cuvant,0);
    }
    return 0;
}