НСД гра-відгадка
Учора у Павла був день народження, і на ньому він з Андрієм грали у наступну гру: Андрій намагався відгадати вік Павла. Андрій знає, що вікт Павла є цілим числом з проміжку від 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).
Вихідні дані
Вивести одне ціле число — кількість спроб, достатніх Андрію відгадати вік Павла у гіршому випадку.