For the given positive integer k find the minimum positive integer n, such that the sum 1 + 2 + 3 + ... + n is divisible by k.
One positive integer k~(k \le 10^8).
Print the minimum possible positive integer n.
Example 1
Example 2