Задачи
Делимость суммы
Делимость суммы
Для заданного натурального значения $k$ найдите наименьшее натуральное число $n$, при котором сумма $1 + 2 + 3 + ... + n$ делится на $k$.
\InputFile
Одно натуральное число $k~(k \le 10^8)$.
\OutputFile
Выведите искомое наименьшее натуральное число $n$.
Входные данные #1
10
Выходные данные #1
4
Входные данные #2
11
Выходные данные #2
10