CF735D.Taxes

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.

芬特先生如今居住在一个税收法律极为特殊的国家。芬特先生今年的总收入为 $ n $（$ n \geq 2 $）布尔，他需缴纳的税额等于 $ n $ 的最大真因子（即不等于 $ n $ 本身的、最大的能整除 $ n $ 的正整数）。例如，若 $ n = 6 $，则芬特先生需缴税 3 布尔；若 $ n = 25 $，则需缴税 5 布尔；而若 $ n = 2 $，则仅需缴税 1 布尔。

由于芬特先生是个非常善于钻营的人，他想稍稍作弊。具体而言，他希望将原始的总额 $ n $ 拆分为若干部分：$ n_1 + n_2 + \dots + n_k = n $（其中 $ k $ 可取任意正整数，甚至允许 $ k = 1 $），并对每一部分单独缴税。但他不能使任一部分等于 1，否则会暴露自己。因此，对所有 $ i = 1, 2, \dots, k $，必须满足 $ n_i \geq 2 $。

奥斯塔普·本德尔想知道：若芬特先生以最优方式将 $ n $ 拆分为若干部分，他最少需要缴纳多少税款？

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

输入的第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot10^9$）——Funt 先生的全年总收入。

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

输出一个整数——Funt 先生需要缴纳的最少税款（单位：burles）。