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

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


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


# V = [(X_i, Y_i), ...]: X_i (mod Y_i)
def remainder(V):
    x = 0; d = 1
    for X, Y in V:
        g, a, b = extgcd(d, Y)
        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
        x %= d
    return x, d


N = I()


def prime_factorization(n):
    ANS = {}
    for i in range(2,int(n**.5)+1):
        if n % i == 0:
            r = 0  # nがiで何回割り切れるか
            while n % i == 0:
                n //= i
                r += 1
            ANS[i] = r
    if n != 1:
        ANS[n] = 1
    return ANS


prime = prime_factorization(N)
if not 2 in list(prime.keys()):
    prime[2] = 1
else:
    prime[2] += 1

A = list(prime.keys())
B = list(prime.values())
l = len(A)


ans = 2*N
from itertools import product

for a in list(product([-1,0],repeat=l)):
    for i in range(l):
        if a[i] != 0:
            break
    else:
        continue

    V = [(a[i],A[i]**B[i]) for i in range(l)]
    x,d = remainder(V)
    ans = min(ans,x)

print(ans)
