CF337E.Divisor Tree

A divisor tree is a rooted tree that meets the following conditions:

• Each vertex of the tree contains a positive integer number.
• The numbers written in the leaves of the tree are prime numbers.
• For any inner vertex, the number within it is equal to the product of the numbers written in its children.

Manao has n distinct integers _a_1, _a_2, ..., a__n. He tries to build a divisor tree which contains each of these numbers. That is, for each a__i, there should be at least one vertex in the tree which contains a__i. Manao loves compact style, but his trees are too large. Help Manao determine the minimum possible number of vertices in the divisor tree sought.

约数树是一种满足以下条件的有根树：

• 树的每个顶点中包含一个正整数；
• 树的叶节点中所写的数均为素数；
• 对任意一个内部顶点，其内所写的数等于其所有子节点中所写数字的乘积。

Manao 有 $n$ 个互不相同的整数 $a_1,\,a_2,\,\dots,\,a_n$。他试图构造一棵约数树，使得该树中包含所有这些数。即：对每个 $a_i$，树中至少存在一个顶点，其内所写的数恰好为 $a_i$。Manao 喜欢简洁风格，但目前他构造的树规模过大。请帮助 Manao 确定所求约数树中顶点数的最小可能值。

The first line contains a single integer n (1 ≤ n ≤ 8). The second line contains n distinct space-separated integers a__i (2 ≤ a__i ≤ 1012).

第一行包含一个整数 $n$（$1 \leq n \leq 8$）。第二行包含 $n$ 个互不相同的、以空格分隔的整数 $a_i$（$2 \leq a_i \leq 10^{12}$）。

Print a single integer — the minimum number of vertices in the divisor tree that contains each of the numbers a__i.

输出一个整数——包含所有数字 $a_i$ 的因子树所需的最少顶点数。

Sample 1. The smallest divisor tree looks this way:

Sample 2. In this case you can build the following divisor tree:

Sample 3. Note that the tree can consist of a single vertex.

样例 1. 最小的因数树如下所示：

样例 2. 此时可以构造如下因数树：

样例 3. 注意，该树可以仅由一个顶点构成。