#include<bits/stdc++.h> //:3
using namespace std;
typedef long long LL;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#define int long long

#define cin in
#define cout out

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


const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const LL inf = 2e9;
const LL mod = 1e9 + 7;
const int N = 2e6 + 11;
const LL INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

int t;
string c;

struct trie{
    int a, b;
    trie* next[26];
    trie(){
		a = 0; b = 0;
		memset(next, 0, sizeof(next));
	}
};

trie* R = new trie;

void insert(trie* node = R, int i = 0){
    if(i == sz(c)){
        node->b++;
        return;
    }

    if(node->next[c[i] - 'a'] == NULL){
        node->next[c[i] - 'a'] = new trie;
        node->a++;
    }
    insert(node->next[c[i] - 'a'], i + 1);
}

bool pop(trie* node = R, int i = 0){
    if(i == sz(c)){
        node->b--;
    }else
    if(pop(node->next[c[i] - 'a'], i + 1)){
        node->next[c[i] - 'a'] = NULL;
        node->a--;
    }

    if(node->b == 0 && node->a == 0 && node != R){
        delete node;
        return 1;
    }
    return 0;
}

int pref(trie* node = R, int i = 0){
    if(i == sz(c))return i;
    if(node->next[c[i] - 'a'] == NULL)return i;
    return pref(node->next[c[i] - 'a'], i + 1);
}

int search(trie* node = R, int i = 0){
    if(i == sz(c))return node->b;
    if(node->next[c[i] - 'a'] == NULL)return 0;
    return search(node->next[c[i] - 'a'], i + 1);
}

void solve(){

    while(cin >> t >> c){
		if(t == 0)insert();
		if(t == 1)pop();
		if(t == 2)cout << search() << "\n";
		if(t == 3)cout << pref() <<"\n";
	}

}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}