#include <fstream>
#include <cstring>

using namespace std;
ifstream cin("trie.in");
ofstream cout("trie.out");

string S;
struct Trie{
	Trie* next[26];
	int a,b;
	Trie(){
		a = 0;
		b = 0;
		memset(next,0,sizeof(next));
		}
};
	Trie* G = new Trie;
void adauga(Trie* nod , unsigned int i){
	if(i == S.length()){ nod->b++; return;}
	if(nod->next[S[i] - 'a'] == NULL){
			nod->next[S[i]-'a'] = new Trie;
			nod->a++;
			}
	adauga(nod->next[S[i]- 'a'],i+1);
}

bool sterge(Trie* nod, unsigned int i){
	if(i == S.length()) nod->b--;
		else if(sterge(nod->next[S[i] - 'a'], i+1)){
			  nod->next[S[i] - 'a'] = NULL;
			  nod->a--;
	}
	if(nod->a == 0 && nod->b == 0 && nod != G){
		delete nod; 
		return 1;
		}
	return 0;
}

int cauta(Trie*nod , unsigned int i){
		if(i  == S.length()) return nod->b;
		if(nod->next[S[i] - 'a']) 
			return cauta(nod->next[S[i] - 'a'], i+1);
}
	
int CMMPr(Trie* nod, unsigned int i){
		if(i == S.length()) return i;
		if(nod->next[S[i] - 'a'] == NULL) return i;
		return CMMPr(nod->next[S[i] - 'a'], i+1);
	}
int main(){
	int x;
	while(cin >> x){
		cin >> S;
		 if (x == 0) adauga(G,0);
		 if(x == 1) sterge(G,0);
		 if (x == 2) cout << cauta(G,0) << '\n';
		 if (x == 3) cout << CMMPr(G,0) << '\n';
	}	
	return 0;
}