#pragma GCC optimize("03")
#include <bits/stdc++.h>

using namespace std;

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

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

string s;
int sz, cod;
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 scoate(nod *x, int p){
	if(p == sz){
		x -> nrcuv--;
		if(x -> nrcuv == 0 && x -> nrson == 0 && x != root){
			delete x;
			return 1;
		}
		return 0;
	}
	if(scoate(x -> son[s[p] - 'a'], p + 1)){
		x -> nrson--;
		x -> son[s[p] - 'a'] = NULL;
		if(x -> nrcuv == 0 && x -> nrson == 0 && x != root){
			delete x;
			return 1;
		}
	}
	return 0;
}

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

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

int main(){
	ios_base::sync_with_stdio(0);
	in.tie(NULL);
	root = new nod();
	while(in >> cod >> s){
		sz = s.size();
		if(cod == 0){
			baga(root, 0);
		} else if(cod == 1){
			scoate(root, 0);
		} else if(cod == 2){
			out << aparitii(root, 0) << '\n';
		} else{
			out << prefix(root, 0) << '\n';
		}
	}
	return 0;
}