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.

Input

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

Output

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

Note

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.