P15082 [ICPC 2024 Chengdu R] Magical Set

You have a magical set that initially contains $n$ distinct integers. You discover that these numbers can generate energy by dividing into their factors. In each step, you can select any number greater than $1$ from the set, remove it, and insert one of its factors. The factor you insert must not be equal to the original number. Additionally, due to the instability of the magical set, your operation must ensure that the numbers in the set remain distinct. Each operation generates one unit of energy, and your goal is to maximize the total energy generated by performing as many operations as possible. Given the initial numbers in the set, determine the maximum amount of energy that can be generated, i.e., the maximum number of operations that can be performed.

The first line contains an integer $n$ ($1 \le n \le 300$), indicating the number of integers in the initial set. The second line contains $n$ distinct integers $a_i$ ($1 \le a_i \le 10^9$), representing the numbers in the initial set.

Output a single integer indicating the maximum amount of energy that can be generated, i.e., the maximum number of operations that can be performed.