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

Input

18

Output

2

18 can be expressed as 5 + 13

Input

17

Output

1

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

Input

35

Output

3

35 can be expressed as 2 + 2 + 31.