Зеник і НСД

Limits: 2 sec., 256 MiB

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

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

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

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

Input

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

Output

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

Constraints

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

Samples

Input (stdin) сopy	Output (stdout) сopy
4	2

Notes

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