output_description: Print the answer in a line.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: from math import sqrt
  from math import ceil
  
  
  def mpfli(N):  # minimum prime factor listのこと
      li = [i for i in range(N + 1)]
      li2 = [i for i in range(N + 1)]
      for i in range(2, ceil(sqrt(N + 1))):
          for j in range(2 * i, N + 1):
              if li[j] == li2[j]:
                  if li[j] % li[i] == 0:
                      li[j] = li[i]
      return li
  
  
  def pfac(n):  # mpf = mpfli(N)
      S = [0] * (n + 1)
      while n != 1:
          m = mpf[n]
          S[m] += 1
          n = n // m
      return S
  
  
  def divofsum(k):
      pk = pfac(k)
      pk2 = pfac(k + 1)
      pk.append(0)
      pp = [pk[i] + pk2[i] for i in range(k + 2)]
      pp[2] -= 1
      return pp
  
  
  def check(k):
      flag = True
      dk = divofsum(k) + [0] * (N - k - 1)
      for i in range(N + 1):
          if dk[i] < pliN[i]:
              flag = False
              break
      return flag
  
  
  N = int(input())
  mpf = mpfli(N)
  pliN = pfac(N)
  mainflag = False
  k = 1
  while mainflag == False:
      k += 1
      mainflag = check(k)
  print(k)
  
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"}]