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}.

提交代码