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*_{1} + *n*_{2} + ... + *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^{9}$) — 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.