h={4=>3,6=>5,12=>11,14=>13,18=>8,20=>19,21=>19,24=>23,25=>23};h.default=7
n=gets.to_i
p n<26 ? h[n] : n%8-1+`factor #{n-8}`.count(' ')-1==0 ? 14 : 8