除数树是满足以下条件的有根树:
- 树的每个顶点都包含一个正整数。
- 写在树的叶子中的数字是素数。
- 对于任何内部顶点,其中的数字等于其子节点中写入的数字的乘积。
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。请注意,树可以由单个顶点组成。