Зеник і НСД

Обмеження: 2 сек., 256 МіБ

Зеник любить числа. А ще більше Зеник любить багато чисел.

Здавалося б, що для щастя потрібно зовсім небагато. Написати собі багато чисел і осягнути дзен. Але ж ні. Приходить Марічка і все псує. Бачте, треба, щоб всі числа були написані в рядок, сума всіх чисел була рівною \(s\), та ще й НСД кожних двох сусідніх чисел відрізнявся від одиниці.

НСД двох чисел — найбільший спільний дільник, найбільше таке ціле число, що обидва числа діляться на нього без остачі.

Допоможіть Зенику визначити максимальну кількість чисел, що він зможе написати, якщо він таки дотримуватиметься умов Марічки.

Вхідні дані

У єдиному рядку задано одне ціле число \(s\) — число, про яке Марічка згадувала у своїх умовах.

Вихідні дані

У єдиному рядку виведіть одне ціле число — максимальна кількість чисел, які може написати Зеник, дотримуючись умов Марічки.

Обмеження

\(2 \le s \le 10^5\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4	2

Примітки

Зеник може написати два числа: 2, 2.