require 'prime'
ps = gets.to_i.prime_division
qs = ps.map(&:first)
if ps[0][0] == 2 and ps[0][1] >= 2
    qs << 4
end
qs.delete(2)
puts qs.min