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
from math import *

def inv(a, m) : 
	
	m0 = m 
	x0 = 0
	x1 = 1

	if (m == 1) : 
		return 0

	# Apply extended Euclid Algorithm 
	while (a > 1) : 
		# q is quotient 
		q = a // m 

		t = m 

		# m is remainder now, process 
		# same as euclid's algo 
		m = a % m 
		a = t 

		t = x0 

		x0 = x1 - q * x0 

		x1 = t 
	
	# Make x1 positive 
	if (x1 < 0) : 
		x1 = x1 + m0 

	return x1 

def findMinX(num, rem, k) : 
	
	# Compute product of all numbers 
	prod = 1
	for i in range(0, k) : 
		prod = prod * num[i] 

	# Initialize result 
	result = 0

	# Apply above formula 
	for i in range(0,k): 
		pp = prod // num[i] 
		result = result + rem[i] * inv(pp, num[i]) * pp 
	
	
	return result % prod 

n = int(input())

ans = 1e18
m = 2*n
i = 1
while(i <= m):
	if(n == i):
		print(i*2 - 1)
		exit(0)
	i *= 2

i = 2
while(i*i <= m):
	if(m % i == 0):
		if(gcd(i, m // i) == 1):
			num = [0, 0]
			rem = [0, 0]
			num[0] = i
			num[1] = m // i
			rem[0] = 0
			rem[1] = m // i - 1
			ans = min(ans, findMinX(num, rem, 2))
			num[0] = m // i
			num[1] = i
			rem[0] = 0
			rem[1] = i - 1
			ans = min(ans, findMinX(num, rem, 2))
	i += 1

print(ans)
