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