You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

小Y要交税。对于一笔金额 $s$，需要缴纳的税款为 $s$ 的最大真因子（真因子：不等于数字本身的因子）。 例如：$s=4$，除去自身最大因子是2；$s=5$ 是质数，除去自身最大因子是1。

现在小Y可以把总收入 $n$ 拆分成若干份收入，每一份金额至少为2。每一份收入单独计税，总税款等于所有份数税款相加。请你帮小Y找到拆分方案（也可不拆分），使得总税款最小，输出这个最小总税款。

💡提示：本题可以借助哥德巴赫猜想分析：任意大于2的偶数都可以拆成两个质数之和。

Format

Input

一行一个正整数 $n$。

Output

一行一个整数，表示最小总税。

Samples

4

2

9

2

27

3

样例解释

样例 1 解释：

方案 1：不拆分，金额为 4，税款 = 2，总税款 = 2。

方案 2：拆成 2+2，两份金额分别计税，每份税款都是 1，总税款 1+1=2。

两种方案最小总税款都是 2，输出 2。

样例 2 解释：

9 可以拆分为 2+7，两份金额分别计税，每份税款为 1，总税款 1+1=2，这是最优方案。

如果不拆分，9 对应的税款 = 3，比 2 更大。

样例 3 解释：

27 无法拆成两份金额（每份≥2），使得两份税款都为 1。最优方案拆成 3+5+19 ，三份金额分别计税，每份税款都是 1，总税款 1+1+1=3。

Limitation

1s, 128MiB for each test case.

数据规模与约定

对于 30% 的分数，2≤n≤100；

对于 50% 的分数，2≤n≤10000；

对于 100% 的分数，2≤n≤2×10^12。