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 math

N=int(input())

ANS=[0,1, 3, 2, 7, 4, 3, 6, 15, 8, 4, 10, 8, 12, 7, 5, 31, 16, 8, 18, 15, 6, 11, 22, 15, 24, 12, 26, 7, 28, 15, 30, 63, 11, 16, 14, 8, 36, 19, 12, 15, 40, 20, 42, 32, 9, 23, 46, 32, 48, 24, 17, 39, 52, 27, 10, 48, 18, 28, 58, 15, 60, 31, 27, 127, 25, 11, 66, 16, 23, 20, 70, 63, 72, 36, 24, 56, 21, 12, 78, 64, 80, 40, 82, 48, 34, 43, 29, 32, 88, 35, 13, 23, 30, 47, 19, 63, 96, 48, 44, 24]


if N==1:
    print(ANS[N])
    exit()


def ff(x):
    L=int(math.sqrt(x))

    FACT=dict()

    for i in range(2,L+2):
        while x%i==0:
            FACT[i]=FACT.get(i,0)+1
            x=x//i

    if x!=1:
        FACT[x]=FACT.get(x,0)+1

    return FACT

# 拡張ユークリッドの互除法.ax+by=gcd(a,b)となる(x,y)を一つ求め、(x,y)とgcd(x,y)を返す.
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1)
    # print(a,b,axy,bxy)
    q,r=divmod(a,b)

    if r==0:
        return bxy,b # a*bxy[0]+b*bxy[1]=b
   
    rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.
    return Ext_Euc(b,r,bxy,rxy)

FACT=ff(N*2)
LIST=[]
for f in FACT:
    LIST.append(f**FACT[f])
    
L=len(LIST)

LANS=1<<60

for i in range(1,(1<<L)-1):
    A=1
    B=1
    for j in range(L):
        if i & (1<<j)!=0:
            A*=LIST[j]
        else:
            B*=LIST[j]
    #print(A,B)
    #print(Ext_Euc(A,-B))
    x,_=Ext_Euc(A,-B)
    x,y=x[0],x[1]
    # ANS=x+B*k

    if x<0:
        x+=(1+abs(x)//B)*B
    #k=(B+x-1)//x
    #ANS=x+B*k
    #print(x,B,k,ANS)
    LANS=min(LANS,x*A)

print(LANS)
    
