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
n = int(input())
if n == 1:
    print(1)
    exit()
if n == 2:
    print(3)
    exit()
n *= 2
ans = n*2

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        return float("INF")
    else:
        return x % m
def calc(b1,m1,b2,m2):
    p = modinv(m1,m2)
    if p == float("INF"):
        return float("INF")
    tmp = (b2-b1)*p%m2
    m = m1*m2
    tmp = (b2-b1)*p%m2
    r = (b1+m1*tmp)%m
    return r

for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        ans = min(ans,calc(0,i,n//i-1,n//i))
        if i != 1:
            ans = min(ans,calc(0,n//i,i-1,i))
print(ans)