В конце учебного года декан каждого факультета Хогвартса должен разместить итоговую сумму очков, набранных студентами своего факультета, на специальном магическом табло в Большом зале. Изначально сумма очков на табло для каждого факультета равна нулю. Для того, чтобы выставить на табло нужную сумму, деканы могут использовать лишь три заклинания:
1) «engorgio 1» (увеличивает сумму на табло на 1);
2) «engorgio 5» (увеличивает сумму на табло на 5);
3) «engorgio \(\times2\)» (увеличивает сумму на табло в 2 раза).
Профессор МакГонагалл знает, что она должна установить для факультета Гриффиндор на табло сумму очков, равную \(n\).
Какова длина кратчайшей последовательности применения заклинаний «engorgio», с помощью которых профессор сможет добиться желаемого результата на табло?
Формат входных данных
На ввод программе подаётся единственное целое неотрицательное число \(n\). Гарантируется, что \(0\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести единственное целое неотрицательное число — наименьшую возможную длину последовательности применения заклинаний «engorgio», позволяющей установить на табло число \(n\) при начальном значении 0.
| № | Входные данные | Выходные данные |
|
1
|
0
|
0
|
|
2
|
2
|
2
|
|
3
|
5
|
1
|
|
4
|
2053
|
12
|