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