Problems
Sum divisibility
Sum divisibility
For the given positive integer $k$ find the minimum positive integer $n$, such that the sum $1 + 2 + 3 + ... + n$ is divisible by $k$.
\InputFile
One positive integer $k~(k \le 10^8)$.
\OutputFile
Print the minimum possible positive integer $n$.
Input example #1
10
Output example #1
4
Input example #2
11
Output example #2
10