require'prime'
a=[0]*(1+n=gets.to_i)
a[0]=1
Prime.each([n,999].min){|e|
	n.downto(e){|i|a[i-e]>0&&a[i]=[a[i-e]+1,a[i]].max}
}
p a[n]-1