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
from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*res=1
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:#どっちかは+でどっちかは-
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)

