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())
  n *= 2
  ans = []
  ans2 = []
  for i in range(2, 32 * 10**6):
      if n % i == 0:
          ans.append(i)
          n //= i
          cnt = 1
          while n % i == 0:
              n //= i
              cnt += 1
          ans2.append(cnt)
  if n != 1:
      ans.append(n)
      ans2.append(1)
  # print(ans)
  # print(ans2)
  l = len(ans)
  for i in range(l):
      ans[i] **= ans2[i]
  # print(ans)
  time = [0 for _ in range(l)]
  
  
  def nex(time):
      for i in range(l):
          if time[i] == 0:
              time[i] = 1
              return time
          else:
              time[i] = 0
      else:
          return "over"
  
  
  can = []
  while time != "over":
      x = 1
      y = 1
      for i in range(l):
          if time[i] == 0:
              x *= ans[i]
          else:
              y *= ans[i]
      # print(x,y)
      X = int(x)
      Y = int(y)
      if x > y:
          rec = []
          while y != 1:
              rec.append(x // y)
              x, y = y, x % y
          # print(rec)
          if rec:
              le = len(rec)
              rec.reverse()
              now = [1, -rec[0]]
              for j in range(1, le):
                  # print(now)
                  now[0], now[1] = now[1], now[0] - now[1] * rec[j]
              # print(now)
              # print(min(abs(X*now[0]),abs(Y*now[1])))
              can.append(min(abs(X * now[0]), abs(Y * now[1])))
      time = nex(time)
  print(min(can))
  
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"}]