Hide

# Problem B

Longest Prime Sum

Given a positive integer $N$, what is the maximum number of terms of a sum consisting only of prime numbers and summing to $N$?

## Input

The first line contains an integer $N$ ($2 \le N \le 10^{18}$).

## Output

Output a single integer – the maximum number of terms in such a sum.

## Explanation of sample 1

The number $5$ can be written as the sum of primes in two ways: $5$ or $2 + 3$. The latter one has two terms, which is more than one term.

Sample Input 1 | Sample Output 1 |
---|---|

5 |
2 |