Иван-Царевич вышел на бой со Змеем Горынычем, у которого в начале сражения (\(t=0\) мин) было \(n\) голов. Василиса Премудрая предупредила Ивана, что Змей потеряет силу и будет повержен, только если у него останется ровно одна голова: ни больше, ни меньше.
У Ивана есть три приёма, каждый из которых занимает ровно 1 мин:
1) удар мечом — Змей теряет 1 голову;
2) удар булавой — Змей теряет 5 голов;
3) заклятие Василисы — у Змея остаётся только половина голов с округлением вниз (из \(x\) голов остаётся \(\displaystyle\left\lfloor \frac{x}{2} \right\rfloor\) голов).
За какое наименьшее время \(t_{\mathrm{min}}\) (в минутах) Иван-Царевич сможет одолеть Змея Горыныча?
Формат входных данных
Программа получает на ввод единственное натуральное число \(n\). Гарантируется, что \(1\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести единственное целое неотрицательное число — наименьшее время \(t_{\mathrm{min}}\) (в минутах), за которое Иван-Царевич сможет одолеть Змея Горыныча.
| № | Входные данные | Выходные данные |
|
1
|
1
|
0
|
|
2
|
3
|
1
|
|
3
|
14
|
3
|
|
4
|
1024
|
9
|