P = list(range(20000+1)) P[0] = 0 P[1] = 0 for i in range(2,20000+1): if i*i>20000:break for j in range(i*i,20000+1,i): P[j] = P[i] Q = [] for i in range(2,20000+1): if P[i]==i: Q.append(i) N = len(Q) Q = [0]+Q M = int(input()) INFTY = 10**5 dp = [[-INFTY for _ in range(M+1)] for _ in range(N+1)] for i in range(N+1): dp[i][0] = 0 if M>1: dp[1][2] = 1 for i in range(2,N+1): for j in range(M+1): dp[i][j] = dp[i-1][j] if j>=Q[i]: dp[i][j] = max(dp[i][j],dp[i-1][j-Q[i]]+1) if dp[N][M]<=0: print(-1) else: print(dp[N][M])