得点: 3 点
問題文
整数 x 的球,通过敲击该球敲将执行以下操作。 如果
- x 不是质数:消灭被敲击的球,并添加写有整数 a 的球和写有整数 b 的球。a, b 是 您也可以写 ab=x 和 a \geq 2, b \geq 2 可以从满足条件的整数中自由选择。
- x 如果是质数:什么也不会发生。
另外,魔法 1 次使用,可以同时敲击当前所有的球。另一方面,除了使用魔法之外,不能以其他方式敲击球。
现在,整数 给出了 N 上写有数字的球有 1 个。你想通过使用几次魔法,将所有球上写的数字变成质数。最少需要进行多少次操作?
制約
- 2 \leq N \leq 10^{12}
- N 是一个整数
入力
输入是按以下格式从标准输入给出的。
N
出力
请打印答案。 到达
入力例 1
42
出力例 1
2
简介, 准备42 上写有数字的球。使用魔法敲击这个球时,例如会进行如下操作。
- 42 上写有数字的球将消失,7 上写有数字的球和 6 的球。
现在,各自有 6, 7 已写入 2 个球。使用魔法敲击这些球时,将会进行如下操作。
- 7 的球也不会发生任何事情。 有
- 6 上写有数字的球将消失,2 上写有数字的球和 3 的球。
现在,各自有 2, 3, 7 已写入 3 个球。由于它们都是质数, 可以通过2 次魔法来达到条件。2 无法在少于次数的情况下达成条件。
入力例 2
48
出力例 2
3
例如,按照下图的步骤进行操作,3 就可以用次数的魔法将所有球上写的数字变为素数。

入力例 3
54
出力例 3
2
入力例 4
53
出力例 4
0
如果一开始就是素数的话,即使不使用魔法也满足条件,0 。 须满足