Sum is Multiple

Given is an integer N. Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N. It can be proved that such a positive integer k always exists.

Constraints

• 1 \leq N \leq 10^{15}
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer in a line.

Examples

Input

11

Output

10

Input

20200920

Output

1100144

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N

outputFormat

Output

Print the answer in a line.

Examples

Input

11

Output

10

Input

20200920

Output

1100144

样例

20200920

1100144