Distinct Prime Summands

Given a positive integer n, find the maximum number of distinct prime numbers which can be used to represent n as their sum.

A prime number, also called a prime, is a positive integer that has no positive divisors other than 1 and itself. For example, $2$, $3$, $5$, $7$, and $13$ are primes, while $4$, $9$, $12$, and $18$ are not.

Even though a prime cannot be factored into a product of other positive integers (aside from $1$ and itself), it can sometimes be expressed as a sum of several other prime numbers. In this problem, you need to compute the maximum number of distinct primes that can sum up to exactly n.

Note: If n is a prime itself, one valid representation is simply {n}. Also, if n is less than 2, then there is no prime number available, and the answer should be 0.

One way to approach the problem is to consider the smallest primes in increasing order and try to form a sum. Let $p_1,p_2,\dots,p_k$ denote the first k smallest primes and let </em>S(k)=p_1+p_2+\cdots+p_k</em>. If $S(k)=n$, then the answer is k. If $S(k) < n$, let $D=n-S(k)$. We try to see if by increasing one of the primes by $D$, we can get another prime which is not already in the set. Formally, if there exists an index $i$ $(1\le i\le k)$ such that $$p_i+D \text{ is prime and } p_i+D \notin \{p_1, p_2, \dots, p_k\},$$ then there is a valid representation with k distinct primes. If not, you have to try a smaller k.

inputFormat

The input consists of a single positive integer n.

Constraints:

• n is a positive integer. (If n < 2, output 0.)

outputFormat

Output a single integer: the maximum number of distinct primes that sum to exactly n.

sample

1

0