問題文

$N$ マスからなるすごろくがあり、$i$ 番目のマスには正の整数 $A_i$ が書かれています。 また、最初は $1$ 番目のマスに駒が置かれています。

このすごろくにおいて、駒は自分のいるマスに書かれた整数と互いに素でない整数が書かれたマスにワープすることができ、それ以外の移動方法はありません。 すごろくが始まる前に、あなたは次の操作を $0$ 回以上何回でも行うことができます。

• $1 \le i \le N$ なる $i$ と正の整数 $m$ を選び、コスト $m$ を支払って $A_i$ を $m$ 倍する。

何回かのワープを使って駒を $1$ 番目のマスから他の $2$ 番目から $N$ 番目の全てのマスに移動できるようにするとき、 かかるコストの総和の最小値を求めてください。

入力

$N$
$A_1\ A_2\ \dots\ A_N$

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5\ (1 \le i \le N)$
• 入力は全て整数である。

出力

コストの総和の最小値を出力し、最後に改行してください。

サンプル

4
1 2 3 4

4

4
6 4 3 9

0

4
3 3 3 5

3

10
42 39 59 67 71 9 78 37 19 4

10