Новогодние подарки - 2

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

Входные данные

В единственной строке задано натуральное число N (3 ≤ N ≤ 100000000).

Выходные данные

Единственное число - наименьшее количество попыток, за которое Снегурочка сможет сравнять содержимое подарков или -1, если сделать это невозможно.

Примеры