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 的质因数。

输出一行一个整数表示答案。

对于样例二，原数组任意两个数之间是纯净的，但是检验时可以让前两个数相乘合并：[60,15]，60 和 15 之间是不纯净的，所以没有通过检验。一种最小花费的方式是令 a_1:=\frac{a_1}{2}，花费是 2，产生新数组 [3,10,15]，可以证明此数组是可以通过检验的。