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