Migrated from Lutece 3024 小组作业真是太好辣

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

某位老师的班级有 $n$ 名学生，第 $i$ 名学生有一个能力值 $a_i$。

他给学生布置小组作业，并提出了奇怪的要求：

• 每个小组的人数必须恰好为 $2$。
• 每名同学必须和所有其它同学各组成一次小组，并提交一份小组作业。

一份小组作业若由学生 $i$ 和 $j$ 提交，这份小组作业的完成度为 $\mathrm{lcm}(a_i,a_j)$。

现在他想知道，所有小组作业的完成度之和对 $998244353$ 取模是多少。

以上是一个幽默的题面。但是为了阅读方便，我们也提供一个官方的题面：

给定一个序列 $a_1,a_2,...,a_n$。求出 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n\mathrm{lcm}(a_i,a_j)$ 对 $998244353$ 取模的结果。

Input

第一行包含一个整数 $n(1\leq n\leq 2\times10^5)$。

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(1\leq a_1,a_2,...,a_n\leq 10^6)$。

Output

输出一行包含一个整数，代表答案对 $998244353$ 取模的结果。

Samples

3
2 4 6

22

Note

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

Resources

2023 UESTC ICPC Training for Math