题目链接：

D. Taxes

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to n (n ≥ 2) burles and the amount of tax he has to pay is calculated as the maximum divisor of n (not equal to n, of course). For example, if n = 6 then Funt has to pay 3 burles, while for n = 25 he needs to pay 5 and if n = 2 he pays only 1 burle.

As mr. Funt is a very opportunistic person he wants to cheat a bit. In particular, he wants to split the initial n in several parts n₁ + n₂ + ... + n_k = n (here k is arbitrary, even k = 1 is allowed) and pay the taxes for each part separately. He can't make some part equal to 1 because it will reveal him. So, the condition n_i ≥ 2 should hold for all i from 1 to k.

Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split n in parts.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 2·10⁹) — the total year income of mr. Funt.

Output

Print one integer — minimum possible number of burles that mr. Funt has to pay as a tax.

Examples

Input

4

Output

2

Input

27

Output

3 题意：一个n可以拆成任意多个数，每个数都不为1，f（n）=最大的因子（除了其本身）；使得拆的和最小； 思路：显然拆成素数会使得解更优，相当于问最少拆成几个素数；根据歌德巴赫猜想；详见代码；

#include
     
      using namespace std;#define ll long long#define mod 1000000007#define esp 0.00000000001const int N=1e5+10,M=1e6+10,inf=1e9;const ll INF=1e18+10;int prime(int n){    if(n<=1)    return 0;    if(n==2)    return 1;    if(n%2==0)    return 0;    int k, upperBound=n/2;    for(k=3; k<=upperBound; k+=2)    {        upperBound=n/k;        if(n%k==0)            return 0;    }    return 1;}int main(){    int x;    scanf("%d",&x);    if(prime(x))        return puts("1");    if(x%2==0)        return puts("2");    if(prime(x-2))        return puts("2");    puts("3");    return 0;}