output_description: Print the answer in a line.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: import sys
  
  
  def make_prime_table(n):  # nまでの整数について，それに含まれる最大の素数
      sieve = list(range(n + 1))
      sieve[0] = -1
      sieve[1] = -1
      for i in range(4, n + 1, 2):
          sieve[i] = 2
      for i in range(3, int(n**0.5) + 1, 2):
          if sieve[i] != i:
              continue
          for j in range(i * i, n + 1, i * 2):
              if sieve[j] == j:
                  sieve[j] = i
      return sieve
  
  
  def prime_factorize(n):  # 1を除く(素因数,指数)のリスト
      result = []
      while n != 1:
          p = prime_table[n]
          e = 0
          while n % p == 0:
              n //= p
              e += 1
          result.append((p, e))
      return result
  
  
  N = int(input())
  prime_table = make_prime_table(N)
  
  if N == 1:
      print(1)
      sys.exit()
  f = prime_factorize(N)
  p, e = f[-1]  # 最大素べき
  # print(p,e)
  P = p**e
  for a in range(1, 10**15 // P):
      k = a * P
      if (k * (k - 1) // 2) % N == 0:
          print(k - 1)
          sys.exit()
      if (k * (k + 1) // 2) % N == 0:
          print(k)
          sys.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"}]