e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Уменьшающееся число

Над целым числом можно производить следующие операции:

1. Если число делится на 3, то делить его на 3;

2. Если число делится на 2, то делить его на 2;

3. Вычитать 1.

По заданному натуральному числу n найти наименьшее количество операций, после выполнения которых получится 1.

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

Каждая строка содержит одно натуральное число n (1n106).

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

Для каждого значения n в отдельной строке вывести наименьшее количество операций, после выполнения которых получится 1.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
1
5
10
Выходные данные #1
0
3
3