Сервис хранит добавляемые коды и обрабатывает запросы к своей базе.

Поддерживаются операции трёх типов:

• 1 x — в сервис добавляется код x;
• 2 x — требуется узнать, сколько раз код x был добавлен к текущему моменту;
• 3 — требуется узнать, сколько различных кодов сейчас хранится в сервисе.

Для каждой операции второго и третьего типа необходимо вывести ответ.

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

В первой строке задано число n — количество операций.

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

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

Для каждой операции типа 2 или 3 выведите ответ на отдельной строке.

Ограничения

• 1 <= n <= 2 * 10^5
• 0 <= x <= 10^9 для операций, в которых присутствует x

Примеры

Пример 1

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

1
3

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

0

Пример 2

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

2
3
2 0

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

0
0