#include <bits/stdc++.h>

#define x first
#define y second
#define VM 100005
#define pb push_back
#define ppb pop_back
#define ll long long
#define pii pair<int, int>

using namespace std;

//don't forget to put input in the file!!!
ifstream fin("trie.in");
ofstream fout("trie.out");

int op;
string word;

struct node{
	char c;
	int cnt, ch;
	node* next[26];
	node* pre;
};

int main(){ 
	node* root = new node();
	node* curr = root;
	while(fin>>op>>word){
		curr = root;
		switch(op){
			case 0:
				for(int i=0; i<word.size(); ++i){
					if(curr->next[word[i] - 'a'] == NULL){
						node* n = new node();
						n->c = word[i]; 
						n->cnt = 0;
						n->pre = curr;
						curr->next[word[i] - 'a'] = n;
						++curr->ch;
					}
					curr = curr->next[word[i] - 'a'];
				}
				++curr->cnt;
				// cout<<curr->c<<' '<<curr->cnt<<'\n';
					break;
			case 1:
				for(int i=0; i<word.size(); ++i){
					if(curr->next[word[i] - 'a'])
						curr = curr->next[word[i] - 'a'];
				}
				--curr->cnt;
				
				node * tmp;
				while(curr->ch == 0 && curr->cnt == 0&&curr!=root){
					// cout<<curr->c<<' '<<curr->cnt<<'\n';
					tmp = curr->pre;
					tmp->next[curr->c - 'a'] = NULL;
					delete curr;
					--tmp->ch;
					curr = tmp;
				}
				// delete curr;
				break;
			case 2:
				int i;
				for(i=0; i<word.size(); ++i){
						if(curr->next[word[i] - 'a']){
							// cout<<curr->c<<' ';
							curr = curr->next[word[i] - 'a'];
						}
						else break;
					}
					// cout<<i<<' ';
					if(i == word.size())
						fout<<curr->cnt<<'\n';
					else fout<<"0 \n";
					break;
			case 3:
				for(i=0; i<word.size(); ++i){
						if(curr->next[word[i] - 'a']){
							// cout<<curr->next[word[i] - 'a']->c<<' ';
							curr = curr->next[word[i] - 'a'];
						}
						else break;
					}
					// if(curr->next[word[i] - 'a'] == NULL || curr->next[word[i] - 'a'] && curr->next[word[i] - 'a']->cnt == 0)	--i;
					fout<<i<<'\n';
					// cout<<curr->cnt<<'\n';
					break;
		}
	}
	
	
	return 0;
}