#include <fstream>
#include <vector>
#include <string>
#define sct 'a'
using namespace std;

typedef class Nod * Arbore;

class Nod
{
public:
	Nod();
	Nod(vector <char> v);
	Arbore fii[30];
	int nr_in_fii[30];
	int nr_aparitii;
	vector <char> val; /// compesia caii
	void adauga(vector <char> v);
	void scoate(vector <char> v);
	int l_prefix(vector <char> v);
	int aparitii(vector <char> v);
	void transf();
};

Nod::Nod()
{
	for (int i = 0; i < 30; i++)
		fii[i] = 0, nr_in_fii[i] = 0;
	nr_aparitii = 1;
}

Nod::Nod(vector<char> v)
{

	Nod();
	if (v.size() == 0) {
		nr_aparitii = 1;
	}
	else {
		val = v;
		nr_aparitii = 0;
	}
}

void Nod::adauga(vector<char> v)
{
	transf();
	if (v.size() == 0)
		nr_aparitii++;
	else {
		int p = *v.rbegin() - sct;
		v.pop_back();
		if (fii[p] == 0)
			fii[p] = new Nod(v);
		else
			fii[p]->adauga(v);
		nr_in_fii[p]++;
	}
}

void Nod::scoate(vector<char> v)
{
	if (v.empty()) {
		nr_aparitii--;
		return;
	}
	int p = *v.rbegin() - sct;
	if (fii[p] == 0)
		return;
	v.pop_back();
	fii[p]->scoate(v);
	nr_in_fii[p]--;
}

int Nod::l_prefix(vector<char> v)
{
	transf();
	if (v.empty())
		return 0;
	int p = *v.rbegin() - sct;
	v.pop_back();
	if (nr_in_fii[p] == 0)
		return 0;
	return 1 + fii[p]->l_prefix(v);
}

int Nod::aparitii(vector<char> v)
{
	if (!val.empty()) {
		if (v == val)
			return 1;
		return 0;
	}
	if (v.empty())
		return nr_aparitii;
	int p = *v.rbegin() - sct;
	if (fii[p] == 0)
		return 0;
	v.pop_back();
	return fii[p]->aparitii(v);
}

void Nod::transf()
{
	if (!val.empty()) {
		int p = *val.rbegin() - sct;
		val.pop_back();
		fii[p] = new Nod(val);
		val.clear();
		nr_in_fii[p]++;
	}
}


int main()
{
	Nod q;
	int n, op;
	ifstream in("trie.in");
	string s;
	ofstream out("trie.out");
	vector <char> v;
	while (in >> op >> s) {
		v.clear();
		for (int i = s.size() - 1; i >= 0; i--)
			v.push_back(s[i]);

		if (op == 0)
			q.adauga(v);
		if (op == 1)
			q.scoate(v);
		if (op == 2)
			out << q.aparitii(v) << '\n';
		if (op == 3)
			out << q.l_prefix(v) << '\n';
	}
	return 0;
}