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