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

Гра на запити НСД

Гра на запити НСД

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

У Чіхмана вчора був день народження (насправді ні) і він грав в гру на вгадування з Куцменом: Куцмен намагався вгадати скільки років виповнилося Чіхману. Куцмен знає, що вік Чіхмана – натуральне число від 1 до n включно. Куцменможе загадати певне число x[і] Чіхман скаже йому НСД цього числа і його віку.

Розглянемо випадок, коли n = 6. Куцмен починає з запиту 3 і Чіхман відповідає, що НСД = 1. Це означає що вік Чіхмана не може бути рівним 3 або 6, але може бути 1, 2, 4, 5. Куцмен дає наступний запит 2, на що Чіхман відповідає, що НСД = 2. Це означає, що вік Чіхмана може бути 2 або 4, але не 1 і 5. Нарешті, Куцмен загадує число 4 і Чіхман відповідає 2. Це означає, що вік Чіхмана точно рівний 2. Таким чином Куцмену знадобилося 3 запити.

Проте, дізнатися вік Чіхмана можна і за 2 запити. Для цього на першому кроці потрібно дати запит 6, після чого, залежно від відповіді, можна легко дізнатися вік не більше ніж одним запитом.

Знайдіть, яку мінімальну кількість запитів потрібно зробити Куцмену в найгіршому випадку, якщо він буде грати оптимально.

Входные данные

В першому рядку задано одне ціле число n (2 ≤ n ≤ 10^7) – максимальний можливий вік Чіхмана.

Выходные данные

Виведіть одне число – мінімальну кількість запитів, необхідну на вгадування віку Чіхмана.

Пример

Входные данные #1
6
Выходные данные #1
2