Prime Cut 2

Prime Cut 2

Any integer larger than 1 can be expressed as the sum of 1 or more non-distinct prime numbers. For example, 18 can be expressed as 5 + 13, whilst 17 is already a sum of prime numbers.

For a given integer, $n$, find the minimum number of prime numbers that would be need to make a sum of $n$.

Input format

One integer is given, $n$. $(1 < n < 1e4)$

Output format

Output the minimum number of prime numbers which would be required to have $n$ as their sum.

Examples

18

2

18 can be expressed as 5 + 13

17

1

As 17 is prime, only 17 is required to express it as a sum of prime numbers

35

3

35 can be expressed as 2 + 2 + 31.