所謂偏序關係，指的是一個集合上 $S$ 的二元關係 $\leq$，滿足以下三個條件：

• 自反性：$\forall a\in S$，有 $a\leq a$；
• 反對稱性：$\forall a, b\in S$，$a\leq b$ 且 $b\leq a$，則 $a = b$；
• 遞移性：$\forall a, b, c\in S$，$a\leq b$ 且 $b\leq c$，則 $a\leq c$。

當我們講到「二維偏序」時，常有個誤解是認為所有偏序關係都能夠被拿來利用。而我們這次要討論的主角──整除關係──就是一個實實在在的反例。

實際上，競程中講到二維偏序時，要求元素要滿足的得是「全序關係」，全序與偏序關係幾乎相同，但其中的「自反性」會被升級為：

• 完全性：$a\leq b$ 或 $b\leq a$。

也就是說，對於任意兩個元素，他們互相要能夠「比較」，才能排出一個順序。理所當然的，在整除關係中，例如當兩個數字是 $2$ 和 $3$ 時，誰都不整除誰，就造成問題了。

現在，給你 $N$ 個數字，為了解決這樣子的麻煩，我們來為這些數字製造整除上的全序關係，具體來說，你可以試圖進行以下操作：

• 選擇一個正整數 $1\leq i<N$ 以及一個質數 $p$，將 $a_i$ 裡 $p$ 的冪次和 $a_{i+1}$ 裡 $p$ 的冪次互換。

也就是說，當兩個數字為 $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}
$$

請輸出這個最少操作次數。