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 typing
def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)
def base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())*2
ans=n-1
i=2
factors=[]
while i*i<=n:
  if n%i==0:
    tmp=1
    while n%i==0:
      n=n//i
      tmp=tmp*i
    factors.append(tmp)
  else:
    i+=1
if n!=1:
  factors.append(n)
for i in range(2**len(factors)):
  s=base10toN(i,2)
  slist=[]
  for j in s:
    slist.append(j)
  slist.reverse()
  for j in range(len(factors)-len(s)):
    slist.append('0')
  left=1
  right=1
  for j in range(len(factors)):
    if slist[j]=='0':
      left=left*factors[j]
    else:
      right=right*factors[j]
  if left*_inv_gcd(left,right)[1]>1:
    ans=min(ans,left*_inv_gcd(left,right)[1]-1)
print(ans)
      