### BUGGY CODE ###

from collections import defaultdict
from itertools import chain, combinations
import numpy as np


def ext_gcd(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 solve(n):
    # sieve
    primes_array = np.ones(10 ** 6, dtype=np.int8)
    primes_array[0] = 0
    primes_array[1] = 0
    for p in range(10 ** 6):
        if primes_array[p] == 1:
            primes_array[p * p::p] = 0
    primes = np.where([primes_array > 0])[1]
    # print(primes)
    # prime factorization
    factorization = defaultdict(int)
    m = 2 * n
    for p in primes:
        while m % p == 0:
            m = m // p
            factorization[p] += 1
    for p in range(10 ** 6, 32 * 10 ** 6):
        if m % p == 0:
            q = m // p
            if p > 1:
                factorization[p] += 1
            if q > 1:
                factorization[q] += 1
            m = 1
            break
    if m > 1:
        factorization[m] += 1
    # print(factorization)
    factor_list = []
    for k in factorization.keys():
        factor_list.append(k ** factorization[k])

    # trivial answer
    if n % 2 == 1:
        res = n - 1
    else:
        res = 2 * n - 1

    # power set
    for s in chain.from_iterable(combinations(factor_list, r) for r in range(len(factor_list) + 1)):
        p = np.int(np.prod(s))
        q = 2 * n // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if x < 0:
            res = min(res, abs(p * x))
            # print(p, q, abs(p * x), q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

from collections import defaultdict
from subprocess import Popen, PIPE
from itertools import chain, combinations
import numpy as np


def ext_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = ext_gcd(b % a, a)
        return g, x - (b // a) * y, y


# from nagiss-san's AC
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(n))
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))


def solve(n):
    factorization_acl = fast_prime_factorization(2 * n)
    factorization = defaultdict(int)
    for f in factorization_acl:
        factorization[f] += 1
    # print(factorization)
    factor_list = []
    for k in factorization.keys():
        factor_list.append(k ** factorization[k])

    # trivial answer
    res = 2 * n - 1

    # power set
    for s in chain.from_iterable(combinations(factor_list, r) for r in range(len(factor_list) + 1)):
        p = np.int(np.prod(s))
        q = 2 * n // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if x < 0:
            res = min(res, abs(p * x))
        else:
            res = min(res, abs(q * y))
        # print(p, q, p * x, q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


if __name__ == "__main__":
    test()
    main()