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]$，可以证明此数组是可以通过检验的。