require 'prime'
$prime_array = Prime.each(999999).flat_map{|v|;v}

def judge_prime_with_index(num)
	return $prime_array.include?(num) ? $prime_array.index(num) + 1 : nil
end

while input = gets
	n = input.strip.to_i
	count = 0
	n.downto(2) {|num|
		result = judge_prime_with_index(num)
		if result != nil
			count = result
			break
		end
	}
	puts count
end