Problem C
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.

5

2