Divisor Tree

给你 $n(n\le 8)$ 个互不相同正整数， $a_1,a_2,a_3,…,a_n(2\le a_i \le10^{12})$ 现在请你构造一棵有根树，每个结点都有一个正整数权值，满足： 1. 这棵树的每个结点的权值都恰好等于其儿子结点的权值的乘积，即： $$\forall x 不是叶子结点 ，val_x=\prod_{s 是 x 的儿子 }val_s$$ 2. 所有叶子节点的权值都是质数 $$\forall x 是叶子结点 ,x 是质数 $$ 3. 能从树上找到 $n$ 个点，使得这些点的权值依次等于 $a_1,a_2,a_3,…,a_n$ 求构造出的树的结点数量最少是多少。

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.

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}<=10^{12} $ ).

Print a single integer — the minimum number of vertices in the divisor tree that contains each of the numbers $ a_{i} $ .

2
6 10

7

4
6 72 8 4

12

1
7

1

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.