//
//  main.cpp
//  trie
//
//  Created by Tereza Oprea on 13/11/2018.
//  Copyright © 2018 Tereza Oprea. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("trie.in");
ofstream fout ("trie.out");

int x;
char s[25];

struct Trie{
    Trie *fii[26];
    int aparitii;
    int nrfii;
    Trie *parinte;
    Trie ( ){
        for (int i=0; i<=25; i++)
            fii[i] = NULL;
        aparitii = 0;
        nrfii = 0;
        parinte = NULL;
    }
};

Trie rad;

void inserare (char *s, Trie &nod){
    if (*s == 0){
        nod.aparitii++;
        return;
    }
    
    if ( nod.fii[(*s) - 'a'] == NULL){
        nod.fii[(*s) - 'a'] = new Trie;
        nod.nrfii++;
        nod.fii[(*s) - 'a']->parinte = &nod;
    }
    
    inserare (s+1, *(nod.fii [(*s) - 'a']));
}

void stergere ( char *s, Trie &nod){
    if (*s == 0){
        nod.aparitii--;
        if (nod.aparitii == 0 && nod.nrfii == 0){
            nod.parinte->nrfii--;
            nod.parinte->fii [(*(s-1)) - 'a'] = NULL;
            delete &nod;
        }
        return;
    }
    stergere (s+1, *(nod.fii [(*s) - 'a']));
    if (nod.nrfii == 0 && &nod != &rad && nod.aparitii == 0){
        nod.parinte->nrfii--;
        nod.parinte->fii [(*(s-1)) - 'a'] = NULL;
        delete &nod;
    }
}

int cautare (char s[], Trie &nod){
    if (*s == 0)
        return nod.aparitii;
    if (nod.fii[(*s) - 'a'] == NULL)
        return 0;
    return cautare (s+1, *(nod.fii [(*s) - 'a']));
    
}

int prefix (char s[ ], Trie &nod){
    if (*s == 0)
        return 0;
    if (nod.fii[(*s) - 'a'] == NULL)
        return 0;
    return prefix (s+1, *(nod.fii[(*s) - 'a'])) + 1;
    
}

int main() {
    while (fin >> x){
        fin >> s;
        if (x == 0)
            inserare( s, rad);
        if (x == 1)
            stergere ( s, rad );
        if (x == 2)
            fout << cautare ( s, rad ) << '\n';
        if (x == 3)
            fout << prefix ( s, rad ) << '\n';
    }
    return 0;
}