require'prime'
a=[0,*[-1]*(n=gets.to_i)]
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]