require 'prime'

N = 20000
dp = Array.new(N+1)
dp[0] = 0

Prime.each(N/4) do | p |
  (N-p).downto(0) do | n |
    next unless dp[n]
    unless dp[n+p]
      dp[n+p] = dp[n] + 1
    else
      dp[n+p] = dp[n] + 1 if dp[n] + 1 > dp[n+p]
    end
  end
end

p dp[gets.to_i] || -1