#!/usr/bin/ruby
N=gets.to_i
if N>25
	p N%8==1&&`factor #{N-8}`.count(' ')<2 ? 14 : 8
else
	h={4=>3,6=>5,12=>11,14=>13,18=>8,20=>19,21=>19,24=>23,25=>23};h.default=7
	p h[N]
end