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
n=int(input())
# 拡張ユークリッド互除法
# gcd(a,b)とax+by=gcd(a,b)の最小整数解を返す
def exgcd(a,b):
    if a==0:
        return b,0,1
    else:
        g,y,x=exgcd(b%a,a)
        return g,x-(b//a)*y,y

# 二元の場合の中国剰余定理
# x≡b1(mod m1)かつx≡b2(mod m2)⇔x≡r(mod m)となる(r,m)を返す
# 解なしの時(0,-1)
def crt(b1,m1,b2,m2):
    d,p,q=exgcd(m1,m2)
    if (b2-b1)%d!=0 or d!=1:
        return 0,-1
    m=m1*(m2//d) # m=lcm(m1,m2)
    tmp=(b2-b1)//d*p%(m2//d)
    r=(b1+m1*tmp)%m
    return r,m

ans=10**18
for num in range(1,2*n+1):
    if num*num>2*n:
        break
    if 2*n%num==0:
        r1,m1=crt(0,num,-1,2*n//num)
        r2,m2=crt(0,2*n//num,-1,num)
        if r1!=0:
            ans=min(r1,ans)
        if r2!=0:
            ans=min(r2,ans)
print(ans)