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
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic

def extgcd(a, b):
  if b:
    d, y, x = extgcd(b, a%b)
    y -= (a//b)*x
    return d, x, y
  else:
    return a, 1, 0
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if min(prod1,prod2)>ans:
    continue
  if min(prod1,prod2)==1:
    ans = min(ans, max(prod1,prod2)-1)
  else:
    d,a1,a2 = extgcd(prod1,prod2)
    ans = min(ans, min(abs(a1*prod1),abs(a2*prod2)))
print(ans)

