2023 软件学院 ACM 集训队筛选赛
Problem B. 偷心贼的净化
Touxinzei 拥有一项技能，能够虏获少女芳心，但是面对自己真爱的女子，却无法施展此技能，为了能够追求到唯一所爱，他需要将自己纯净化......
有 n 个正整数 a，若两个数的 gcd 可以写成 p^k 的形式( p 是 1 或质数，k 为正整数)，那么便称这两个数之间是纯净的。
Touxinzei 会通过此方式检验数组 a 是否纯净：
- 从数组 a 中，选择两个 gcd 不为 1 的数相乘，并用相乘的结果替换这两个数。此操作可以进行若干次或不进行。
若用上述方法可以产生一个数组 a' ，使得数组 a' 存在两个数之间是不纯净，那么便判定原数组 a 是不纯净。
在进行检验前，Touxinzei 可以进行若干次如下操作：
- 选择第 i 个数 a_i ，并选择 a_i 的一个质数因子 x ，令 a_i:=\frac{a_i}{x}，该操作需要花费 x。
为了使数组 a 是纯净的，最小花费是多少。
输入
输入一行一个整数 n(1\leq n \leq 10^5)。
第二行输入 n 个整数 a_i (1\leq a_i\leq 10^{9})，且保证 a_i 不存在大于 1000 的质因数。
输出
输出一行一个整数表示答案。
样例
| 标准输入 复制文本 |
9 9 9 8 2 4 4 3 5 3 |
| 标准输出 复制文本 |
0 |
| 标准输入 复制文本 |
3 6 10 15 |
| 标准输出 复制文本 |
2 |
提示
对于样例二，原数组任意两个数之间是纯净的，但是检验时可以让前两个数相乘合并：[60,15]，60 和 15 之间是不纯净的，所以没有通过检验。一种最小花费的方式是令 a_1:=\frac{a_1}{2}，花费是 2，产生新数组 [3,10,15]，可以证明此数组是可以通过检验的。
登录以提交代码。