d=0,*[-1]*n=gets.to_i
999.times{|p|n.downto(p){|i|t=d[i-p]+1;t>0&&d[i]<t&&d[i]=t}if p==2||2**~-p%p==1}
p d[n]