Задача E. Подарок ≡

Условие

Тимофей очень любит числа, являющиеся точными степенями двойки и тройки. У него даже есть два альбома, в которых хранятся карточки с этими числами: в первом можно найти 1, 2, 4, 8, 16 и так далее, а во втором — 1, 3, 9, 27 и так далее.

Тимофей хочет подарить папе число n, составленное из суммы чисел на этих карточках. Поскольку ему жалко расставаться со своими числами, он хочет подарить папе наименьшее число своих карточек, числа на которых в сумме дают n. Сколько карточек Тимофей подарит папе?

Формат входных данных

Единственная строка входного файла содержит одно натуральное число n.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу.

Ограничения

1 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 40 баллов.

Пояснения к примерам

В первом примере число два можно составить двумя способами: 1 + 1 или 2. Тимофей выберет второй способ и передаст папе одну карточку с двойкой.

Во втором примере есть способ (не единственный) представить число 79 в виде набора из четырех карточек: 79 = 64 + 9 + 4 + 2. Меньшим набором карточек обойтись нельзя.

Примеры тестов

2

1

79

4