Prime Collector

配点 : $600$ 点

問題文

mts くんは mojacoder 国のギルドに所属する勇者です。

ギルドではクエストを受注することができ、クエストをクリアすると報酬が貰えます。クエストの詳細は下記の通りです。

• ギルドには $N$ 個のクエストがあり、$1$ から $N$ までの番号がついています。ゲームの世界ではよくあるように、あるクエストを受注してクリアしても、そのクエストは再び受注できます。
• $i$ 番目のクエストをクリアすると、正の整数 $A_i$ の素因数を一つ選んで報酬として貰うことができます。同じクエストを再び受注してクリアすれば同様にして報酬が貰えます。異なるクエストに同じ正の整数が割り当てられている可能性があります（サンプル $2$ を確認してください）。

mts くんはコンプリート欲があるため、クエストを繰り返しクリアすることで全埋めをしようとしています。全埋めとは、下記の二つの条件を達成することです（前述した通り、同じクエストは何度でも受注できます）。

• $N$ 個のクエストを全てクリアする
• $N$ 個のクエストの報酬として入手可能な全ての種類の素因数を集める

mts くんは凄腕の勇者なので受注したクエストは必ずクリアできます。このとき、mts くんが全埋めするために受注するクエストの個数の最小値を求めてください。

制約

• $1 \leq N \leq 10^4$
• $2 \leq A_i \leq 10^6$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

出力

全埋めするために受注するクエストの個数の最小値を出力してください。

サンプル 1

2
4 6

2

$4$ の素因数は $\{ 2 \}$、$6$ の素因数は $\{ 2, 3 \}$ です。
例えば、下記のように $2$ 個のクエストを受注することで全埋めできます。
$2$ 個未満のクエストで全埋めすることはできません。

• クエスト $1$ を受注、クリアして素因数 $2$ を貰う
• クエスト $2$ を受注、クリアして素因数 $3$ を貰う

サンプル 2

3
5 5 6

4

$5$ の素因数は $\{ 5 \}$、$6$ の素因数は $\{ 2, 3 \}$ です。
例えば、下記のように $4$ 個のクエストを受注することで全埋めできます。
$4$ 個未満のクエストで全埋めすることはできません。

• クエスト $1$ を受注、クリアして素因数 $5$ を貰う
• クエスト $2$ を受注、クリアして素因数 $5$ を貰う
• クエスト $3$ を受注、クリアして素因数 $2$ を貰う
• クエスト $3$ を受注、クリアして素因数 $3$ を貰う

サンプル 3

4
42 55 17017 17

7

サンプル 4

6
2 6 385 33 3 65

7