N = int(input()) def dpsum(N): if N == 1: return -1 pn = [2] for i in range(3,N+1,2): for s in pn: if i%s == 0:break else:pn += [i] Q = [1]+[0]*N for p in pn: for i in range(N,-1,-1): if p > 0 and i+p <= N: Q[i+p] = max(Q[i+p], Q[i]+1) return Q[N]-1 print(dpsum(N))