该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem G. 你说的对，但是不如莫反

时间限制 : 2000 ms

空间限制 : 256 MB

题目背景

以下文字仅为娱乐，与题目本身无关。

你说的对，但是感觉不如莫反。莫比乌斯反演，是一种数论技巧。设 $\tau$ 是狄利克雷卷积单位元 $\tau(x)=[x=1]$，$u$ 是乘法单位元函数 $u(x)=1$，则莫比乌斯函数 $\mu$ 定义为 $u$ 在狄利克雷卷积下的逆元，即 $\mu * u=\tau$。莫比乌斯反演归根到底就是对于数论函数$f,g$，有 $f=g*u\Longleftrightarrow g=f*\mu$（这里 * 是狄利克雷卷积运算）。你的数学很差，我现在每天用莫反都能求 1e5 次数据规模 1e12 的积性函数前缀和，每个月差不多 3e6 次反演变换，也就是现实生活中 3e18 次加法运算，换算过来最少也要算 1000 年。虽然我只有 14 岁，但是已经超越了中国大多数人（包括你）的水平，这便是莫反给我的骄傲的资本。

题目描述

pzr 刚刚学会了莫比乌斯反演，使用莫比乌斯反演的技巧，可以很快地对于一个数组求出

等信息。

现在，他想对于长度为 $n$ 的 $a$ 数组求出：

其中，$\gcd(a_i,a_j)$ 表示 $a_i$ 和 $a_j$ 的最大公约数。公式 $[s]$ 在命题 $s$ 为真时取 $1$，其余时刻取 $0$。

换句话说，我们每次选出数组中任意两个下标 $(i, j)$（$i$ 可以等于 $j$），且满足 $\gcd(a_i,a_j)\ge 300$ 。 对于任意这样的 $(i, j)$，都可以计算出 $a_i\times a_j\times \gcd(a_i,a_j)$ 的值，请求出它们的和。

由于答案过大，请对 998244353 取模后输出。

输入格式

第一行一个整数 $n$，表示数组的长度。

接下来一行 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，表示这个数组。

输出格式

仅包含一个整数，表示公式对 998244353 取模的结果。

样例输入1

8
5 4 3 2 1 500 2000 9997

样例输出1

996717796

样例 1 解释

最大公约数大于 $300$ 的取值方案有以下几种：

$(i,j)=(6,6)\to (a_i,a_j)=(500, 500):\gcd=500$，对答案的贡献为 $500^3$

$(i,j)=(6,7)\to (a_i,a_j)=(500,2000):\gcd=500$，对答案的贡献为 $500\times 2000\times 500$

$(i,j)=(7,6)\to (a_i,a_j)=(2000,500):\gcd=500$，对答案的贡献为 $500\times 2000\times 500$

$(i,j)=(7,7)\to (a_i,a_j)=(2000,2000):\gcd=2000$，对答案的贡献为 $2000^3$

$(i,j)=(8,8)\to (a_i,a_j)=(9997,9997):\gcd=9997$，对答案的贡献为 $9997^3$

答案的总和为 1008225269973，对 $998244353$ 取模的结果是 996717796。

样例输入2

10
5000 2000 1000 2000 9999 1000 19998 29997 39996 49995

样例输出2

750967481

数据范围与约定

$1\le n,a_i\le 10^5$