require 'prime'

class Integer
	def miller_rabin_prime?(k=100)
		n = abs
		return true if n == 2
		return false if n < 2 || n % 2 == 0
		d = n-1
		d /= 2 while d % 2 == 0
		k.times{
			a = rand(1..n-1)
			t = d
			y = Integer.mod_pow(a, t, n)
			while t != n-1 && y != 1 && y != n-1
				y = y ** 2 % n
				t *= 2
			end
			return false if y != n-1 && t % 2 == 0
		}
		return true
	end
	def self.mod_pow(base, pow, mod)
		result = 1
		while pow > 0
			result = result * base % mod if pow % 2 == 1
			base = base ** 2 % mod
			pow /= 2
		end
		return result
	end
end

h = {
    4 => 3,
    6 => 5,
    8 => 7,
    9 => 7,
    10 => 7,
    12 => 11,
    14 => 13,
    15 => 7,
    16 => 7,
    18 => 8,
    20 => 19,
    21 => 19,
    22 => 7,
    24 => 23,
    25 => 23
}

n = gets.to_i
if h[n]
	puts h[n]
elsif n%8 == 1 && (n-8).miller_rabin_prime?
	puts 14
else
	puts 8
end