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
def euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return a0, b0

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

num=n
for i in range(2,max(10,n)):
    if(i*i>n):
        if(num!=1):
            soinsu.append([num,1])
        break
    if(num%i!=0):
        continue
    cnt=0
    while(num%i==0):
        cnt+=1
        num//=i
    soinsu.append([i,cnt])

kazu=len(soinsu)
#print(soinsu,kazu)


ans=[]
for i in range(2**(kazu-1)):
    a=1
    for j in range(kazu):
        if((i&1<<j)!=0):
            a*=soinsu[j][0]**soinsu[j][1]
    b=n//a
    c,d=euclid(a,b)
    if(c*d==0):
        c+=b
        d+=a
    ans.append(max(a*c,b*d))
    #print(a,b,c,d)


if(kazu==1):
    print(min(ans)-2)
else:
    print(min(ans)-1)