N=gets.to_i
r=[0,0]
2.upto(Math.sqrt(N)){|i|(i+i).step(N,i){|j|r[j]=0} unless r[i]}
m=[]
r.each_with_index{|v,i|m<<i unless v}
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