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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2
1
2
79
4

0.106s 0.025s 15