Поиск по префиксу

Вам дан словарь, который изначально не содержит ни одного слова. Необходимо обработать последовательность запросов, каждый из которых относится к одному из двух типов:

1. Запрос типа 1: Добавить слово в словарь.

   • Input: 1 word (1 ≤ |word| ≤ 1000), where word is a non-empty string consisting of lowercase English letters.

   • Action: Add the word to the dictionary.

2. Запрос типа 2: Посчитать количество слов, начинающихся с заданного префикса.

   • Input: 2 prefix (1 ≤ |prefix| ≤ 1000), where prefix is a non-empty string consisting of lowercase English letters.

   • Output: Output the number of words in the dictionary that start with the given prefix.

- Формат ввода: 2 prefix (1 ≤ |prefix| ≤ 1000), где prefix — непустая строка из строчных букв английского алфавита.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 100000), обозначающее количество запросов.

В следующих n строках даны сами запросы. Каждая строка имеет один из следующих форматов:

• 1 word для запроса типа 1.

• 2 prefix для запроса типа 2.

Гарантируется, что общее количество символов во входных данных не превышает .

Выходные данные

Для каждого запроса типа 2 выведите в отдельной строке одно целое число — количество слов в словаре, начинающихся с данным префиксом.

Пример