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
inpl = lambda: list(map(int,input().split()))
from math import sqrt, ceil, gcd
def divisors(n, sort=True, reverse=False):
    sqn = int(ceil(sqrt(n)))
    div_list = []
    if sqn*sqn == n:
        div_list.append(sqn)
    for i in range(1,sqn):
        if n % i == 0:
            div_list.append(i)
            div_list.append(n//i)
    if sort:
        div_list.sort(reverse=reverse)
    return div_list

def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

N = int(input())
M = 2*N
divlist = divisors(M)
kmin = M-1
for p in divlist:
    q = M // p
    if p == 1 or q == 1 or gcd(p,q) > 1:
        continue
    else:
        m = q - inv_mod(p, q)
        k = p*m
        if k < kmin:
            kmin = k
print(kmin)
