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
input = sys.stdin.readline

n = int(input()) * 2
D = []

for i in range(2, int(n**0.5) + 1):
    d = 1
    while n%i == 0:
        n //= i
        d *= i
    if d != 1:
        D.append(d)
    if n == 1:
        break
if n != 1:
    D.append(n)
# print(D)

# 拡張Euclidの互除法。ap + bq = gcd(a, b) となる p, q, d=gcd(a, b) を返す。
def extgcd(a, b):
    if b == 0:
        return 1, 0, a
    q, p, d = extgcd(b, a%b)
    q -= (a // b) * p
    return p, q, d

def crt(R, M):  # 中国剰余定理。Rは余り、Mは割る数の配列。不定なら(0,1)、不能なら(0,0)が返る。
    r = 0
    m = 1
    for i in range(len(R)):
        p, _, d = extgcd(m, M[i])
        if (R[i] - r) % d != 0:
            return (0, 0)
        tmp = (R[i] - r) // d * p % (M[i] // d)
        r += m * tmp
        m *= M[i] // d
    return (r % m, m)


ans = float("inf")

# Rs = []

for i in range(1, 2**len(D)):
    ib = format(i, "b").zfill(len(D))
    R = [0] * len(D)
    for j in range(len(D)):
        if ib[j] == "1":
            R[j] = D[j]-1
    ans = min(ans, crt(R, D)[0])
print(ans)