小A有一个包含 N 个正整数的序列 A={A_{1},A_{2},...,A_{N}}。小A每次可以花费 1 个金币执行以下任意一种操作：

• 选择序列中一个正整数 A_i (1\le i\le N)，将 A_i 变为 A_{i}\times P， P 为任意质数；
• 选择序列中一个正整数 A_i (1\le i\le N)，将 A_i 变为 \frac{A_{i}}{P}， P 为任意质数，要求 A_i 能整除 P。

小A想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。

第一行一个正整数 N，含义如题面所示。

第二行包含 N 个正整数 A_{1},A_{2},...,A_{N} 代表序列 A。

输出一行，代表最少需要花费的金币数量。

说明/提示

数据范围

• 对于 60\% 的测试点，保证 1 \le N, A_{i} \le 100。
• 对于所有测试点，保证 1 \le N, A_{i} \le 10^{5}。