import sys



sys.setrecursionlimit(10**7)

def I(): return int(sys.stdin.readline().rstrip())

def MI(): return list(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)

import sys

from itertools import product

def I(): return int(sys.stdin.readline().rstrip())





def ext_gcd(a, b):

    if b:

        d, y, x = ext_gcd(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 = ext_gcd(d, Y)

        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)

        x %= d

    return x, d





def prime_factorization(n):

    res = {}

    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

            res[i] = r

    if n != 1:

        res[n] = 1

    return res





N = I()



prime_fac = prime_factorization(N)

if 2 in list(prime_fac.keys()):

    prime_fac[2] += 1

else:

    prime_fac[2] = 1



# prime_fac = 2*N の素因数分解

# 2*N|k*(k+1)

# 中国剰余定理を用いる



A = list(prime_fac.keys())

l = len(A)



ans = 2*N



for a in list(product([-1,0],repeat=l)):

    V = [(a[i],A[i]**prime_fac[A[i]]) for i in range(l)]

    x,d = remainder(V)

    if x != 0:

        ans = min(ans,x)



print(ans)

import sys

sys.setrecursionlimit(10**7)


def I():
    return int(sys.stdin.readline().rstrip())


def MI():
    return list(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**0.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)

import sys
from itertools import product


def I():
    return int(sys.stdin.readline().rstrip())


def ext_gcd(a, b):
    if b:
        d, y, x = ext_gcd(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 = ext_gcd(d, Y)
        x, d = (Y * b * x + d * a * X) // g, d * (Y // g)
        x %= d
    return x, d


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


N = I()
prime_fac = prime_factorization(N)
if 2 in list(prime_fac.keys()):
    prime_fac[2] += 1
else:
    prime_fac[2] = 1
# prime_fac = 2*N の素因数分解
# 2*N|k*(k+1)
# 中国剰余定理を用いる
A = list(prime_fac.keys())
l = len(A)
ans = 2 * N
for a in list(product([-1, 0], repeat=l)):
    V = [(a[i], A[i] ** prime_fac[A[i]]) for i in range(l)]
    x, d = remainder(V)
    if x != 0:
        ans = min(ans, x)
print(ans)

- -sys.setrecursionlimit(10**7) +from itertools import product -def MI(): -    return list(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): +def ext_gcd(a, b): -        d, y, x = extgcd(b, a % b) +        d, y, x = ext_gcd(b, a % b) -        g, a, b = extgcd(d, Y) +        g, a, b = ext_gcd(d, Y) -N = I() - - -    ANS = {} +    res = {} -            ANS[i] = r +            res[i] = r -        ANS[n] = 1 -    return ANS +        res[n] = 1 +    return res -prime = prime_factorization(N) -if not 2 in list(prime.keys()): -    prime[2] = 1 +N = I() +prime_fac = prime_factorization(N) +if 2 in list(prime_fac.keys()): +    prime_fac[2] += 1 -    prime[2] += 1 -A = list(prime.keys()) -B = list(prime.values()) +    prime_fac[2] = 1 +# prime_fac = 2*N の素因数分解 +# 2*N|k*(k+1) +# 中国剰余定理を用いる +A = list(prime_fac.keys()) -from itertools import product - -    for i in range(l): -        if a[i] != 0: -            break -    else: -        continue -    V = [(a[i], A[i] ** B[i]) for i in range(l)] +    V = [(a[i], A[i] ** prime_fac[A[i]]) for i in range(l)] -    ans = min(ans, x) +    if x != 0: +        ans = min(ans, x)