所謂偏序關係，指的是一個集合上 $S$ 的二元關係 $\leq$，滿足以下三個條件：
當我們講到「二維偏序」時，常有個誤解是認為所有偏序關係都能夠被拿來利用。而我們這次要討論的主角──整除關係──就是一個實實在在的反例。
實際上，競程中講到二維偏序時，要求元素要滿足的得是「全序關係」，全序與偏序關係幾乎相同，但其中的「自反性」會被升級為：
也就是說，對於任意兩個元素，他們互相要能夠「比較」，才能排出一個順序。理所當然的，在整除關係中，例如當兩個數字是 $2$ 和 $3$ 時，誰都不整除誰，就造成問題了。
現在，給你 $N$ 個數字，為了解決這樣子的麻煩，我們來為這些數字製造整除上的全序關係，具體來說，你可以試圖進行以下操作：
也就是說，當兩個數字為 $p^ x\cdot u$ 和 $p^ y\cdot v$ 時，對這兩個數字選擇質數 $p$ 進行操作後，這兩個數字就會變成 $p^ y\cdot u$ 和 $p^ x\cdot v$。注意到這裡必須將所有 $p$ 的冪次提出，也就是前面提到的 $u$ 和 $v$ 不能是 $p$ 的倍數。
為了讓整個序列有全序關係，你的目標是使用最少次的操作，使得：
$$
\forall 1\leq i < j \leq N,\ a_{i}\mid a_{j}
$$
請輸出這個最少操作次數。
輸入首行有一個正整數 $N$，代表數字的個數。
次行 $N$ 個正整數 $a_1, a_2, \ldots, a_N$，代表給你的 $N$ 個數字。
輸出最少的操作次數，使得 $\forall 1\leq i < j \leq N,\ a_{i}\mid a_{j}$。
5 8 4 1 2 2
7
8 4 9 24 18 4 9 6 9
23
10 15 1 3 2 4 25 6 10 7 6
36
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 3~8 | $N\leq 500$，所有 $a_i$ 的質因數都是 $2$ | 6 |
| 3 | 3~13 | 所有 $a_i$ 的質因數都是 $2$ | 23 |
| 4 | 3~19 | 所有 $a_i$ 的質因數都是 $2$ 或 $3$ | 14 |
| 5 | 0~8, 20~31 | $N\leq 500$ | 16 |
| 6 | 32~42 | $a_i\leq 10^ 4$ | 20 |
| 7 | 0~59 | 無額外限制 | 21 |