import scala.collection.mutable
import scala.io.StdIn

object Problem308 {

  def primesIn(max: Int): Seq[Int] = {
    val a = Array.fill(max + 1)(false)
    for {
      i <- 2 to max
      if !a(i)
    } yield {
      (i + i to max by i).foreach(a(_) = true)
      i
    }
  }

  def isPrime(n: BigInt): Boolean = n.isProbablePrime(50)

  def canGoal(n: Int, mod: Int): Boolean = {
    val start = 1
    val goal = n

    val clear = Array.fill(n + 1)(false)
    val primes: Seq[Int] = primesIn(n)

    if (primes.contains(n) || primes.contains(mod + 1)) return false

    def canMoveTo(i: Int): Boolean = !primes.contains(i)
    def left(i: Int): Option[Int] = {
      val next = i - 1
      if (canMoveTo(next) && next % mod != 0 && next >= start) Some(next) else None
    }
    def right(i: Int): Option[Int] = {
      val next = i + 1
      if (canMoveTo(next) && i % mod != 0 && next <= goal) Some(next) else None
    }
    def up(i: Int): Option[Int] = {
      val next = i - mod
      if (canMoveTo(next) && next >= start) Some(next) else None
    }
    def down(i: Int): Option[Int] = {
      val next = i + mod
      if (canMoveTo(next) && next <= goal) Some(next) else None
    }

    val queue = mutable.Queue[Int]()
    queue += start

    while (queue.nonEmpty) {
      val p = queue.dequeue()

      def a: (Int) => Unit = { x =>
        if (!clear(x)) {
          queue += x
          clear(x) = true
        }
      }
      left(p).foreach(a)
      right(p).foreach(a)
      up(p).foreach(a)
      down(p).foreach(a)
    }

    clear(goal)
  }

  def blute(n: Int): Option[Int] = {
    (1 to n) find { mod =>
      canGoal(n, mod)
    }
  }

  def proc(n: BigInt): BigInt = {
    if (n <= 25) {
      BigInt(blute(n.toInt).get)
    } else {
      if (isPrime(n - 8) && (n % 8 == 1 || isPrime(n - 1))) 14 else 8
    }
  }

  def main(args: Array[String]) {
    val n = BigInt(StdIn.readLine())
    val result: BigInt = proc(n)
    println(result)
  }
}