Description

Little 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 needed 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 one integer representing the answer.

5
12 30 48 36 18

4

10
72 81 27 90 45 45 27 99 45 18

6

4
1 2 4 8

2

Hint

"Sample 1 Explanation"

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

"Constraints and Notes"

This problem uses bundled testdata.

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

For all test points, the time limit is 1s and the memory limit is 128MB.

"Source"

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

Translated by ChatGPT 5