Для заданого натурального значення k знайдіть найменше натуральне число n, при якому сума 1 + 2 + 3 + ... + n ділиться на k.

Вхідні дані

Одне натуральне число k (k ≤ 108).

Вихідні дані

Виведіть шукане найменше натуральне число n.