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