require'prime'
n=gets.to_i
dp=[-1]*-~n
dp[0]=0
Prime.each(n){|p|
	(n-p).downto(0){|i|
		dp[i+p]=dp[i]+1 if dp[i]>=0 and dp[i+p]<dp[i]+1
	}
}
p dp[n]