// Trie.cpp : Defines the entry point for the console application.
//
#include <fstream>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <stdlib.h>

std::ifstream fin("trie.in");
std::ofstream fout("trie.out");

class Node
{
public:
	char letter;
	int app_nr;
	int endings;

	std::vector<Node*> sons;

    Node()
    {
        endings = 0;
        sons = std::vector<Node*>(27, (Node*)NULL);
    }

	Node(char letter)
	{
		this->letter = letter;
		this->app_nr = 0;
		this->endings = 0;
		sons = std::vector<Node*>(27, (Node*)NULL);
	}


};


int const MAX_N = 22;
Node *root, *cpy_root;

void add_word(std::string word)
{

    for (size_t i = 0; i < word.length(); i++) {

        int letter = int(word[i] - 'a');

        if (root->sons[letter] == NULL)
        {
            root->sons[letter] = new Node(word[i]);

        }
        root = root->sons[letter];
        root->endings++;
    }

    root->app_nr++;

}

void remove_word(std::string word)
{
    for (size_t i = 0; i < word.length(); i++)
    {

        int letter = int(word[i] - 'a');
        Node *son = root->sons[letter];
        if (root != cpy_root)
            if (root->endings == 0)
            {
                delete root;
                root = NULL;

            }
        root = son;
        root->endings--;
    }

    root->app_nr--;

}

int get_app_nr(std::string word) {

    for (size_t i = 0; i < word.length(); i++)
    {
        int letter = int(word[i] - 'a');

        if (root->sons[letter])
            root = root->sons[letter];
        else
            return 0;
    }

    return root->app_nr;
}


int get_prefix(std::string word)
{
    int prefix = 0;

    for (size_t i = 0; i < word.length(); i++)
    {

        int letter = int(word[i] - 'a');
        if (root->sons[letter] && root->sons[letter]->endings)
        {
            root = root->sons[letter];
            prefix = i + 1;
        }
        else
            break;
    }

    return prefix;
}
void proccess_command(int command, std::string word)
{

	if (command == 0) {
        add_word(word);
	}

	if (command == 1)
		remove_word(word);


	if (command == 2)
		fout << get_app_nr(word) << '\n';

	if (command == 3)
		fout << get_prefix(word) << '\n';

}




int main()
{

	root = new Node();
	cpy_root = root;

	char line[MAX_N];

	while (fin.getline(line, MAX_N))
	{
		char delim[] = " ";
		int command = atoi(strtok(line, delim));
		std::string word(strtok(NULL, delim));

		proccess_command(command, word);
		root = cpy_root;
	}

    return 0;
}