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