# 20000以下の素数を用いたナップサック N = int(input()) F = [True] * (N + 1) F[0] = False F[1] = False facts = [] for i in range(2, N + 1): if F[i]: facts.append(i) for j in range(i * i, N + 1, i): F[j] = False dp = [-1] * (N + 1) dp[0] = 0 for f in facts: for i in range(N, -1, -1): if dp[i] == -1: continue if i + f > N: continue dp[i + f] = max(dp[i + f], dp[i] + 1) print(dp[N])