#include<fstream>
#include<queue>
#include<string>
using namespace std;
ifstream in("trie.in");
ofstream out("trie.out");
const int Nmax=2600000;
struct{
	int val;
	int fii;
	int p[26];
} T[Nmax];int K=1;
queue<int> q;
int ind(char z){return (int)(z-'a');}
int alloc(){
	int u;
	if(!q.empty()){
		u=q.front();
		q.pop();
	}
	else u=++K;
	return u;
}
void Adauga(string x){
	int I=1;
	for(unsigned int i=0;i<x.length();i++){
		int c=ind(x[i]);
		if(!T[I].p[c]){
			T[I].p[c]=alloc();
			T[I].fii++;
		}
		I=T[I].p[c];
	}
	T[I].val++;
}
void Sterge(string x){
	int sterg[30];
	int I=1;
	sterg[0]=1;
	for(unsigned int i=0;i<x.length();i++){
		int c=ind(x[i]);
		I=T[I].p[c];
		sterg[i+1]=I;
	}
	T[I].val--;
	int das=1;
	for(unsigned int i=x.length();i>=1 && das;i--){
		das=0;
		int c=ind(x[i-1]);
		if(T[sterg[i]].val==0 && T[sterg[i]].fii==0){
			das=1;
			T[sterg[i-1]].p[c]=0;
			T[sterg[i-1]].fii--;
			q.push(sterg[i]);
		}
	}
}
int Aparitii(string x){
	int I=1;
	for(unsigned int i=0;i<x.length();i++){
		int c=ind(x[i]);
		if(T[I].p[c]) I=T[I].p[c];
		else return 0;
	}
	return T[I].val;
}
int LungPrefix(string x){
	int L=0;
	int I=1;
	for(unsigned int i=0;i<x.length();i++){
		int c=ind(x[i]);
		if(T[I].p[c]) I=T[I].p[c];
		else return i;
	}
	return x.length();
}
int main(){
	int c;
	string s;
	while(in>>c){
		in>>s;
		if(c==0) Adauga(s);
		if(c==1) Sterge(s);
		if(c==2) out<<Aparitii(s)<<'\n';
		if(c==3) out<<LungPrefix(s)<<'\n';
	}
	return 0;
}