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$.

Input

One positive integer $k(k\le 10^8)$.

Output

Print the minimum possible positive integer $n$.

Examples