#include <bits/stdc++.h>

using namespace std;

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

struct nod {
	int nrson;
	int nrcuv;
	nod *son[26];
	nod() {
		nrson = 0;
		nrcuv = 0;
		memset(son, 0, sizeof son);
	}
};

int sz, cod;
string s;
nod *root;

void baga(nod *x, int p) {
	if (p == sz) {
		x -> nrcuv++;
		return;
	}
	if (x -> son[s[p] - 'a'] == NULL) {
		x -> son[s[p] - 'a'] = new nod();
		x -> nrson++;
	}
	baga(x -> son[s[p] - 'a'], p + 1);
}

bool sterge(nod *x, int p) {
	if (p == sz) {
		x -> nrcuv--;
		if (x -> nrson == 0 && x -> nrcuv == 0 && x != root) {
			delete x;
			return 1;
		}
		return 0;
	}
	if (sterge(x -> son[s[p] - 'a'], p + 1)) {
		x -> nrson--;
		x -> son[s[p] - 'a'] = NULL;
		if (x -> nrson == 0 && x -> nrcuv == 0 && x != root) {
			delete x;
			return 1;
		}
		return 0;
	}
	return 0;
}

int ap(nod *x, int p) {
	if (p == sz)
		return x -> nrcuv;
	if (x -> son[s[p] - 'a'] == NULL)
		return 0;
	return ap(x -> son[s[p] - 'a'], p + 1);
}

int pref(nod *x, int p) {
	if (p == sz || x -> son[s[p] - 'a'] == NULL)
		return 0;
	return 1 + pref(x -> son[s[p] - 'a'], p + 1);
}

int main() {
	root = new nod();
	while (in >> cod >> s) {
		sz = s.size();
		if (cod == 0) {
			baga(root, 0);
			continue;
		}
		if (cod == 1) {
			sterge(root, 0);
			continue;
		}
		if (cod == 2) {
			out << ap(root, 0) << '\n';
			continue;
		}
		if (cod == 3) {
			out << pref(root, 0) << '\n';
			continue;
		}
	}
	return 0;
}