Shashank loves prime numbers. Prime numbers are positive integers that have exactly two distinct positive divisors.

Whenever he gets bored, he takes a number n and represent that number as sum of prime numbers. He want to use minimum number of primes in his representation. The prime numbers used need not to be distinct.

You have to help Shashank by calculating the minimum number of primes required to represent the n as sum of primes.

Input Format

First line contains integer, n

Output Format

Output a single integer, which is answer to the problem

Constraints

• 3 ≤ n ≤ 10⁹
• n is odd