require 'prime'
n = gets.to_i

if Prime.prime?(n) then puts n-1
else

isBreak = false
i = 1
j = 1

cnt = 0
while true do
cnt_k = 0
while cnt_k<=cnt do
  if (i+cnt_k)*(j+cnt-cnt_k)==n then
    isBreak = true
    break
  end
  cnt_k += 1
end
break if isBreak
cnt += 1
end

puts cnt
end