← 返回题目列表

Codeforces · 735/D

D. 税收

中文机器翻译题面 查看原题

Funt 先生现在居住在一个有着非常具体税法的国家。先生的总收入这一年的Funt等于n(n≥2)个burles,他要缴纳的税额按n的最大除数计算(当然不等于n)。例如,如果 n = 6,则 Funt 必须支付 3 个伯尔,而如果 n = 25,他需要支付 5 个伯尔,如果 n = 2,他只需支付 1 个伯尔。

作为先生。 Funt是一个非常机会主义的人,他想欺骗一下。特别是,他想把最初的n分成几部分n1 + n2 + ... + nk = n(这里k是任意的,甚至k = 1也可以),并为每一部分分别纳税。他不能让某个部分等于 1,因为这会暴露他的身份。因此,对于从 1 到 k 的所有 i,条件 ni ≥ 2 应该成立。

Ostap Bender 想知道,如果 Funt 选择将 n 分成几部分的最佳方式,他必须支付多少钱(即最少)。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 2·109) — 先生的一年总收入。芬特。

输出

打印一个整数 — 先生的最小可能数量。 Funt 必须缴纳税款。

示例

输入 #1

4

输出 #1

2

输入 #2

27

输出 #2

3