Дано натуральное число N. Над ним можно произвести следующий набор операций:
вычитать единицу;
делить на три, если число кратно трем;
делить на два, если число четное.
После выполнения одной из операций к полученному результату также можно применить указанные операции, и делается это до тех пор, пока результат не окажется равным 1.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N (N ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите наименьшее количество операций, в результате выполнения которых будет получена единица.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5
3
2
1
0
3
10
3
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
