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