require 'prime'

def extgcd(a, b)
  if b.zero?
    [1, 0, a]
  else
    x, y, d = extgcd(b, a % b)

    [y, x - (a / b) * y, d]
  end
end

N = gets.to_i

if N.prime?
  if N == 2
    puts 3
  elsif N == 1
    puts 1
  else
    puts N - 1
  end
else
  primes = (2 * N).prime_division
  values = primes.map { |e, cnt| e ** cnt }
  cnt = primes.size
  ans = Float::INFINITY
  min_val = Float::INFINITY

  if primes.size == 1
    puts 2 * N - 1
    exit
  end

  (1 << cnt).times do |mask|
    a = 1
    b = 1

    cnt.times do |i|
      if mask[i] == 0
        a *= values[i]
      else
        b *= values[i]
      end
    end

    next if min_val < a
    break if min_val < b

    x, y, _ = extgcd(a, b)
    v1 = a * x.abs
    v2 = b * y.abs
    s = v1 * v2

    if s > 0 && min_val > s
      min_val = s
      ans = v1
      ans = v2 if v1 > v2
    end
  end

  puts ans
end
