Задача A. Большая распродажа

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

В магазине "Программист-спортсмен" большая распродажа! В преддверии поступления товаров нового сезона, нужно срочно освободить полки и витрины, продавая прошлогодние коллекции по бросовым ценам. К сожалению, установить произвольную цену на товар нельзя, в соответствии с антимонопольным законом на распродажу распространяются следующие условия:

1) На товар можно установить любую скидку (от 1 до 99 процентов) по сравнению с ценой товара в предыдущий день.

2) И скидка, и новая стоимость товара должны являться натуральными числами.

Например, если товар стоит 20 рублей, на него можно установить скидку 25% и на следующий день этот товар будет продаваться по 15 рублей. А вот скидку в 30% установить нельзя — новая цена будет выражаться дробным числом рублей.

Молодой программист Тимофей каждый день после работы заходит в магазин и скупает все товары, которые сегодня стоят 1 рубль. Как скоро хозяину магазина удастся снизить стоимость товара с n рублей до 1 рубля?

Формат входных данных

Единственная строка входных данных содержит натуральное число n — начальная стоимость товара в рублях. Гарантируется, что это значение таково, что существует последовательность корректных скидок, снижающих стоимость товара до 1 рубля.

Формат выходных данных

Выведите одно натуральное число — наименьшее количество дней, необходимых для максимального снижения стоимости товара.

Ограничения

2 ≤ n ≤ 1018

Пояснение к примеру

В примере дана начальная стоимость товара 125 рублей. В первый день на него устанавливается скидка 96% и товар продается по цене 5 рублей. Во второй день скидка составит 80% и вечером товар будет куплен Тимофеем за 1 рубль.

Примеры тестов

Стандартный вход Стандартный выход
1
125
2

0.086s 0.017s 15