問題文

長さ $N$ の整数列 $A_0,A_1,\\cdots,A_{N-1}$ があります。 次式の値を求めてください。

• $\\sum_{i=0}^{N-2} \\sum_{j=i+1}^{N-1} \\mathrm{lcm}(A_i,A_j)$

ここで、$\\mathrm{lcm}(x,y)$ は、$x$ と $y$ の最小公倍数を意味します。 なお、答えは非常に大きくなることがあるので、$998244353$ で割ったあまりを求めてください。

制約

• $1 \\leq N \\leq 200000$
• $1 \\leq A_i \\leq 1000000$
• 入力される値はすべて整数である。

入力

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

$N$ $A_0\\ A_1\\ \\cdots\\ A_{N-1}$

出力

$\\sum_{i=0}^{N-2} \\sum_{j=i+1}^{N-1} \\mathrm{lcm}(A_i,A_j)$ の値を $998244353$ で割ったあまりを出力せよ。

入力例 1

3
2 4 6

出力例 1

22

$\\mathrm{lcm}(2,4)+\\mathrm{lcm}(2,6)+\\mathrm{lcm}(4,6)=4+6+12=22$ です。

入力例 2

8
1 2 3 4 6 8 12 12

出力例 2

313

入力例 3

10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

出力例 3

353891724