require "prime"

def ok n,w
  stack = []
  vis = n.times.map { false }
  stack.push 1
  while stack.size != 0
    c = stack.pop
    return true if c == n
    vis[c] = true
    if c%w != 0 && !vis[c+1] && !$isprime[c+1]
      stack.push c+1
    end
    if c%w != 1 && !vis[c-1] && !$isprime[c-1]
      stack.push c-1
    end
    if c-w >= 1 && !vis[c-w] && !$isprime[c-w]
      stack.push c-w
    end
    if c+w <= n && !vis[c+w] && !$isprime[c+w]
      stack.push c+w
    end
  end
  false
end

n = gets.to_i

$isprime = n.times.map { false }
Prime.each(n) { |p| $isprime[p] = true }

Prime.each(n) do |w|
  if ok n,w
    puts w
    exit
  end
end

puts n