Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Divisor Tree

time limit per test

0.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Examples

Input

2

6 10

Output

7

Input

4

6 72 8 4

Output

12

Input

1

7

Output

1

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2021 02:15:52 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|