e-olymp
Competitions

Just Math easy contest

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 (k108).

Output

Print the minimum possible positive integer n.

Time limit 1 second
Memory limit 128 MiB
Input example #1
10
Output example #1
4
Input example #2
11
Output example #2
10