题目描述

小 A 有一个包含 $N$ 个正整数的序列 $A=(A_1,A_2,\dots,A_N)$。小 A 每次可以花费 $1$ 个金币执行以下任意一种操作：

• 选取序列中一个元素 $A_i$（$1\le i\le N$），并选择任意质数 $p$，将 $A_i$ 变为 $A_i\times p$（相当于给 $A_i$ 乘以一个质因子）；
• 或者选取序列中一个元素 $A_i$（$1\le i\le N$），并选择任意质数 $p$（要求 $p\mid A_i$），将 $A_i$ 变为 $\frac{A_i}{p}$（相当于把 $A_i$ 的一个质因子除去）。

也就是说，每次操作可以向某个数中添加或删除一个质因子，费用为 $1$。小 A 希望通过若干次操作（每次花费 $1$）把序列中的所有整数变为相同的数。求使序列变为所有元素相等所需的最小金币数。

输入格式

• 第一行包含一个正整数 $N$。
• 第二行包含 $N$ 个正整数 $A_1,A_2,\dots,A_N$，表示初始序列。

输出格式

输出一行，包含一个整数：把序列所有元素变为相同所需的最少金币数。

样例输入

5
10 6 35 105 42

样例输出

8

说明

数据范围

• 对于 $60\%$ 的数据，保证 $1\le N,A_i\le 100$；
• 对于所有数据，保证 $1\le N,A_i\le 10^5$。