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
from collections import defaultdict
N = int(input())

# ax + by = d
# d,x,y
def gcd(a,b):
    if b == 0:
        return a, 1, 0
    s = a % b
    t = a // b
    d, x, y = gcd(b, s)
    x,y = y, x -  t * y
    if d < 0:
        d,x,y = -d,-x,-y
    return d, x, y 

if N == 1:
    print(1)
    exit()

def divisors(n):
    ls = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            ls.append(i)
            ls.append(n//i)
    ls = sorted(list(set(ls)))
    return ls

M = 2*N
divs = divisors(M)

if len(divs) == 2:
    pass

ans = 10**20
for m1 in divs:
    m2 = M // m1 
    d,t1,t2 = gcd(-m1,m2)
    if d > 1:
        continue
    if t1 > 0:
        ans = min(ans, m1*t1)

print(ans)

    
    
    


