НОД игра-угадайка
Вчера у Павла был день рождения, и на нем он с Андреем играл в следующую игру: Андрей старался угадать возраст Павла. Андрей знает, что возраст Павла является целым числом в промежутке от 1 до n включительно. Андрей может назвать любое число x между 1 и n, а Павел скажет ему значение наибольшего общего делителя x и его возраста.
Рассмотрим один из возможных исходов игры для n = 6. Андрей называет 3, Павел отвечает, что НОД 3 и его возраста, равен 1. Значит возраст Павла не может быть ни 3, ни 6, но может равняться 1, 2, 4 или 5. Андрей продолжает игру называя 2, на что Павел отвечает 2. Возраст Павла не может равняться 1 или 5, остались только два варианта - 2 и 4. Наконец, Андрей называет 4, Павел отвечает 2. Следовательно возраст Павла 2, игра окончена.
В приведенном примере Андрею понадобилось три попытки. Однако Павлу достаточно двух попыток при n = 6. Оптимальная стратегия Андрея следующая: сначала следует сказать 6. Если Павел ответит 1, тогда ответом будет 1 или 5, который можно определить назвав 5. Если Павел скажет 2, то ответом будет 2 или 4, и его можно найти назвав 4. Если Павел скажет 3, тогда ответом будет 3. Если Павел скажет 6, то ответ 6.
Найдите наименьшее количество попыток, достаточное Андрею в худшем случае найти ответ для заданного значения n.
Входные данные
Входные данные содержат одно целое число n (2 ≤ n ≤ 10000).
Выходные данные
Вывести одно целое число — количество попыток, достаточное Андрею угадать возраст Павла в худшем случае.