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≤108).
Print the minimum possible positive integer n.