#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#define MAX 100003
using namespace std;


	ifstream fin;
	ofstream fout;

struct Trie{
	int freq;
	Trie* children[26];
	Trie(): freq{0} {
		memset(children, 0, sizeof(children));
	}
};


void insert(char* ptr, Trie* t){

	if(*ptr == 0){
		t -> freq++;
	}
	else{
		int idx = *ptr - 97;

		if((t -> children)[idx] == nullptr)
			(t -> children)[idx] = new Trie;
		
		insert(ptr + 1, (t -> children)[idx]);
	}
}


bool empty(Trie* t){
	bool is_empty = true;
	for(auto child: t -> children){
		if((child != nullptr) && (!empty(child))){
			is_empty = false;
		}
	}

	if(t -> freq)
		is_empty = false;

	return is_empty;
}

void remove(char* ptr, Trie* t){
	if(*ptr == 0){
		t -> freq--;
	}
	else{
		int idx = *ptr - 97;

		if((t -> children)[idx] == nullptr)
			fout << "Error: word not in trie" << "\n";		
		else
			remove(ptr + 1, (t -> children)[idx]);
	}

	for(auto& child: t -> children){
		if((child != nullptr) && empty(child)){
			delete child;
			child = nullptr;
		}
	}


}




void query_freq(char* ptr, Trie* t){
	if(*ptr == 0){
		fout << t -> freq << "\n";
	}
	else{
		int idx = *ptr - 97;

		if((t -> children)[idx] == nullptr)
			fout << 0 << "\n";		
		else
			query_freq(ptr + 1, (t -> children)[idx]);

	}
}


void query_prefix(char* ptr, Trie* t, int deep){
	if(*ptr == 0){
		fout << deep << "\n";
	}
	else{
		int idx = *ptr - 97;

		if((t -> children)[idx] == nullptr)
			fout << deep << "\n";		
		else
			query_prefix(ptr + 1, (t -> children)[idx], deep + 1);

	}
}




int main(){
	fin.open("trie.in");
	fout.open("trie.out");
	int v[MAX];
	char line[30];
	char c;
	Trie root;



	while(fin.getline(line, sizeof(line))){
		switch(line[0]){
			case '0': insert(line + 2, &root); break;
			case '1': remove(line + 2, &root); break;
			case '2': query_freq(line + 2, &root); break;
			case '3': query_prefix(line + 2, &root, 0); break;
		}
	}

}