← 返回题目列表

Codeforces · 337/E

E. 除数树

中文机器翻译题面 查看原题

除数树是满足以下条件的有根树:

- 树的每个顶点都包含一个正整数。
- 写在树的叶子中的数字是素数。
- 对于任何内部顶点,其中的数字等于其子节点中写入的数字的乘积。

Manao 有 n 个不同的整数 a1, a2, ..., an。他尝试构建一个包含每个数字的除数树。也就是说,对于每个 ai,树中应该至少有一个包含 ai 的顶点。马瑙喜欢紧凑的风格,但他的树太大了。帮助马瑙确定所寻找的除数树中可能的最小顶点数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 8)。第二行包含 n 个不同的空格分隔整数 ai (2 ≤ ai ≤ 1012)。

输出

打印单个整数 — 包含每个数字 ai 的除数树中顶点的最小数量。

示例

输入 #1

2
6 10

输出 #1

7

输入 #2

4
6 72 8 4

输出 #2

12

输入 #3

1
7

输出 #3

1

注意

示例 1。最小除数树如下所示:

示例 2。在这种情况下,您可以构建以下除数树:

示例 3。请注意,树可以由单个顶点组成。