Problem Background

Xiao E is playing a number game.

Problem Description

Xiao E has $n$ positive integers $a_1, a_2, \dots, a_n$. He can perform the following operation any number of times:

Choose a number $q$ and a set $S = \{d_1, d_2, \dots, d_m\}$ such that $a_{d_1}, a_{d_2}, \dots, a_{d_m}$ are divisible by $q$, and divide $a_{d_1}, a_{d_2}, \dots, a_{d_m}$ by $q$.

• $q$ must be in the form $p^z$ where $p$ is a prime number and $z$ is a positive integer.

Find the minimum number of operations required to make all these numbers equal.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output an integer representing the answer.

Sample Input and Output

Sample Input #1

5
12 30 48 36 18

Sample Output #1

4

Sample Input #2

10
72 81 27 90 45 45 27 99 45 18

Sample Output #2

6

Sample Input #3

4
1 2 4 8

Sample Output #3

2

Notes

Sample 1 Explanation

The initial sequence is 12 30 48 36 18.
Choose $S=\{4,5\}, p=3$, the sequence becomes 12 30 48 12 6.
Choose $S=\{1,3,4\}, p=2$, the sequence becomes 6 30 24 6 6.
Choose $S=\{2\}, p=5$, the sequence becomes 6 6 24 6 6.
Choose $S=\{3\}, p=2^2=4$, the sequence becomes 6 6 6 6 6.
A total of 4 operations, the method is not unique.

Data Range and Constraints

This problem uses batched testing.

For $100\%$ of the data, $1 \leq n \leq 10^5$, $1 \leq a_i \leq 10^6$.

For all test cases, the time limit is 1 second, and the memory limit is 128MB.

Source

Sweet Round 03 B.
idea & solution: ET2006 & Alex_Wei.

见题面 Input 部分

见题面 Output 部分