N=gets.to_i
r,m=[],[]
2.upto(N){|i|(m<<i;(i+i).step(N,i){|j|r[j]=0}) unless r[i]}
e={0=>0}
m.each{|v|
  f=true
  g=e.clone
  e.each{|w,x|
    z=v+w
    if z<=N&&(!g[z]||g[z]<x+1)
      g[z]=x+1
      f=false
    end
  }
  break if f
  e=g
}
p e[N]||-1