import java.math.BigInteger

fun main() {
    val n = readLine()!!.toLong()
    if (n == 1L) {
        println(1L)
        return
    }
    var f = 1L
    var answer = BigInteger.valueOf(if (n % 2L == 1L) n else (2L * n))
    val factorSet = mutableSetOf<Long>()
    while (f * f <= n) {
        if (n % f == 0L) {
            factorSet.add(f)
            factorSet.add(n / f)
        }
        f++
    }
    val factors = factorSet.toList().sorted()
    fun totient(k: Long): Long {
        var k = k
        var res = 1L
        for (p in factors) {
            if (p != 1L && k % p == 0L) {
                res *= p - 1L
                k /= p
                while (k % p == 0L) {
                    res *= p
                    k /= p
                }
            }
        }
        return res
    }
    fun check(g: Long, h: Long) {
        //println("g = $g, h = $h")
        answer = minOf(answer, BigInteger.valueOf(g) * g.pow(totient(h) - 1L, h))
        //println(answer)
        answer = minOf(answer, BigInteger.valueOf(h) * h.pow(totient(g) - 1L, g))
        //println(answer)
    }
    for (f in factors) {
        if (f != 1L && f != n && f * f <= n && gcd(f, n / f) == 1L) {
            when {
                f % 2L == 0L -> check(2L * f, n / f)
                (n / f) % 2L == 0L -> check(f, 2L * (n / f))
                else -> check(f, n / f)
            }
        }
    }
    println(answer - BigInteger.ONE)
}

fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)

fun Long.pow(power: Long, mod: Long): BigInteger {
    val mod = BigInteger.valueOf(mod)
    var e = power
    var b = BigInteger.valueOf(this) % mod
    var res = BigInteger.ONE
    while (e > 0) {
        if (e and 1L != 0L) {
            res *= b
            res %= mod
        }
        b *= b
        b %= mod
        e = e shr 1
    }
    return res
}