from functools import lru_cache # お好みで。あると同じ素因数分解をするときに楽できる。

# 参考1: https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
# 参考2: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# 参考3: https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def is_prime(n):
    "Miller Rabin primality test. 2 <= n <= 2 ** 64 is required"
    if n % 2 == 0:
        return n == 2
    d = n - 1
    r = (d & -d).bit_length() - 1
    d >>= r

    # witnesses をいい感じに決める。
    if n < 2152302898747:
        if n < 9080191:
            if n < 2047:
                witnesses = [2]
            else:
                witnesses = [31, 73]
        else:
            if n < 4759123141:
                witnesses = [2, 7, 61]
            else:
                witnesses = [2, 3, 5, 7, 11]
    else:
        if n < 341550071728321:
            if n < 3474749660383:
                witnesses = [2, 3, 5, 7, 11, 13]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17]
        else:
            if n < 3825123056546413051:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    # witnesses の決定終了

    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x *= x
            x %= n
            if x == n - 1:
                break
        else:
            return False
    return True


@lru_cache() # お好みで。
def find_factor(n):
    "Find a non-trivial factor of n by using Pollard's rho algorithm."
    m = int(n ** 0.125) + 1
    c = 1
    while True:
        y = 1
        r = 1
        q = 1
        g = 1
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            for k in range(0, r, m):
                ys = y
                for _ in range(m):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
                if g != 1:
                    break
            else:  # 残りの k から r までをやる
                ys = y
                for _ in range(r-k):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
            r *= 2

        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = gcd(x - ys, n)

        if g == n:
            c += 1  # c を変えて続行。
        else:  # g は n の非自明な素因数。
            return g


prime_numbers_200 = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 
    89, 97, 101, 103, 107, 109, 113, 127, 131, 
    137, 139, 149, 151, 157, 163, 167, 173, 179, 
    181, 191, 193, 197, 199
]

def fac(n, try_small_factor = True):
    """
    引数 n の素因数分解をして、素因数を昇順に格納したリストを返す。
    ex. fac_small(60) == [2, 2, 3, 5]
    計算量は O(n ^ 1/4) 程度。
    """
    if n == 1:
        return []
    if is_prime(n):
        return [n]

    ret = []
    if try_small_factor:
        for p in prime_numbers_200:
            while n % p == 0:
                ret.append(p)
                n //= p
            if n == 1:
                return ret

    while n != 1 and not is_prime(n):
        f = find_factor(n)
        if is_prime(f):
            while n % f == 0:
                ret.append(f)
                n //= f
        elif is_prime(n // f):
            ret.append(n // f)
            n = f
        else:
            return sorted(ret + fac(f, False) + fac(n // f, False))

    if n == 1:
        return sorted(ret)
    else:
        ret.append(n)
        return sorted(ret)


N = int(input())
if N == 1:
    print(1)
    exit()
N *= 2
factors = fac(N)
rps = []
index = 0
while index < len(factors):
    f = factors[index]
    tmp = f
    index += 1
    while index < len(factors) and factors[index] == f:
        tmp *= f
        index += 1
    rps.append(tmp)

k = 10 ** 18

b = len(rps)
for i in range(1 << b):
    x = 1
    for j in range(b):
        if i & (1 << j):
            x *= rps[j]
    y = N // x
    m = pow(x, -1, y)

    n = (m * x + 1) // y
    if m == 0 or n == 0:
        m += y
        n += x
    k = min(m * x, k)
    if k * (k - 1) % N == 0:
        k -= 1
    # print(x, y, m * x)
    
print(k)

Measured memory_bytes: 9948