Делимость суммы

Очень простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

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

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

Одно натуральное число $k (k \leq 1 0^{8})$ .

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

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Отправки 4K

Коэффициент принятия 31 %