require "prime"

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