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
import sys
readline = sys.stdin.buffer.readline

n=int(readline())*2

def extgcd(a,b):
	if b==0:
		return (a,1,0)
	else:
		g,y,x=extgcd(b,a%b)
		y-=a//b*x
		return (g,x,y)

def sub(p):
	q=n//p
	g,x,y=extgcd(p,q)
	if g==1:
		x=-x
		while x<=0:
			x+=q
			y+=p
		return x*p
	else:
		return 10**18

ans=10**18
d=1
while d*d<=n:
	if n%d==0:
		ans=min(ans,sub(d),sub(n//d))
	d+=1

print(ans)
