output_description: Print the answer in a line.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: n = int(input())
  k = n
  d = dict()
  for num in range(2, n + 1):
      if num * num > n:
          break
      cnt = 0
      while k % num == 0:
          k //= num
          cnt += 1
      if cnt > 0:
          d[num] = cnt
  if k > 0:
      d[k] = 1
  maxi = 0
  for num in d:
      maxi = max(maxi, num)
  maxi = maxi * d[maxi]
  for i in range(1, n + 1):
      if i * i > n:
          break
      if (i * maxi - 1) * (i * maxi) % (2 * n) == 0:
          print(i * maxi - 1)
          exit()
      if 2 * (i * maxi) * (i * maxi + 1) % (2 * n) == 0:
          print(i * maxi)
          exit()
  
problem_description: Statement
  
  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.
samples: [{"input": "11", "output": "10\n    \n\n1+2+\\cdots+10=55 holds and 55 is indeed a multple of N=11. There are no\npositive integers k \\leq 9 that satisfy the condition, so the answer is k =\n10.\n\n* * *"}, {"input": "20200920", "output": "1100144"}]