Sum divisibility#8747

Sum divisibility

1 second
128 megabytes
Very easy

For the given positive integer find the minimum positive integer , such that the sum 1 + 2 + 3 + ... + n is divisible by .

Input

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

Output

Print the minimum possible positive integer .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading