eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

НСД гра-відгадка

НСД гра-відгадка

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Учора у Павла був день народження, і на ньому він з Андрієм грали у наступну гру: Андрій намагався відгадати вік Павла. Андрій знає, що вікт Павла є цілим числом з проміжку від 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 (2n10000).

Вихідні дані

Вивести одне ціле число — кількість спроб, достатніх Андрію відгадати вік Павла у гіршому випадку.

Приклад

Вхідні дані #1
6
Вихідні дані #1
2