Розкладаючи цукерки у пакунки, Дід Мороз поклав в перший пакунок 1 цукерку, в 2-й – 2, … в N-й – N. Чи зможе Снігурка, докладаючи щоразу в будь-які два різних пакунки по одній цукерці, зробити однаковими кількості цукерок в усіх подарунках?

Вхідні дані

В єдиному рядку записане натуральне число N (3 ≤ N ≤ 100000000).

Вихідні дані

Єдине число - найменша кількість разів, за яку Снігурка зможе зрівняти вміст подарунків або -1, якщо це зробити неможливо.