require "prime"

N = gets.to_i
dp = Array.new(N + 1, -Float::INFINITY)
dp[0] = 0
Prime.each(499) {|p|
  (N - p).downto(0).each {|i| dp[i + p] = [dp[i + p], dp[i] + 1].max}}
ans = [dp[N], -1].max
puts ans