e-olymp
Змагання

Just Math easy contest

Подільність суми

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

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
10
Вихідні дані #1
4
Вхідні дані #2
11
Вихідні дані #2
10