require 'prime'
n = gets.strip.to_i
if n.prime_division[0][0] == 2
	if n.prime_division[0][1] == 1
		puts n.prime_division[1][0]
	else
		if n.prime_division.length > 1 && n.prime_division[1][0] == 3 
			puts 3
		else
			puts 4
		end
	end
else
	puts n.prime_division[0][0]
end