有一块电量为 n 的充电宝，她计划将全部电量分配给若干次充电操作。
每次使用电量 a_i （ a_i \geq 1 ）进行充电时，会产生一定的电量损失，损失量为函数 f(a_i) ，其中：

f(x) 表示 x 的最大真因子（即除 x 本身外的最大正因数）。

特别地：

• 若 x = 1 ，则规定 f(1) = 1 （因为 1 没有真因子，但题目说明“只充 1 点，损失也为 1”）。

目标是：将总电量 n 完全分配为若干个正整数之和（即 a_1 + a_2 + \cdots + a_k = n ），使得总损失
\sum_{i=1}^{k} f(a_i)
最小。

请你求出这个最小的总损失电量。

一行，一个正整数 n （ 2 \leq n \leq 2 \times 10^9 ）。

一行，一个整数，表示最小可能的总损失电量。

样例 1解释：

• 方案 1：一次充 4 → 损失 f(4) = 2 （4 的最大真因子是 2）
• 方案 2：充 2 + 2 → 损失 f(2) + f(2) = 1 + 1 = 2
• 方案 3：充 1+1+1+1 → 损失 1+1+1+1 = 4
• 最小损失为 2。

样例 2解释：

• 最优方案：分成 2 + 7
  • f(2) = 1 ， f(7) = 1 （7 是质数，最大真因子为 1）
  • 总损失 = 1 + 1 = 2
• 或 3 + 3 + 3 → f(3)=1 ，总损失 = 3
• 所以最小为 2。

说明 / 提示

• 2 \leq n \leq 2 \times 10^9
• f(x) = \begin{cases} 1, & \text{if } x \text{ 是质数 or } x = 1 \ \dfrac{x}{p}, & \text{其中 } p \text{ 是 } x \text{ 的最小质因数} \end{cases}
• 关键观察：质数的损失为 1，是最小单位损失。
• 因此，问题转化为：将 n 拆分为尽可能多的质数之和，以最小化总损失（每个质数贡献 1）。

数学背景：根据哥德巴赫猜想（已被验证至极大范围），

• 若 n 为偶数且 n \geq 4 ，可拆成两个质数 → 损失为 2；
• 若 n 为奇数：
  • 若 n 本身是质数 → 损失为 1；
  • 否则，若 n - 2 是质数 → 拆成 2 + (n−2)，损失为 2；
  • 否则 → 拆成 3 + 偶数（≥4），该偶数可拆为两质数 → 总共 3 个质数，损失为 3。

因此，答案只能是 1、2 或 3。

二级