#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define SIZE 1000100
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define int long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
const int mod = 998244353;
int n, inv[SIZE] = { 0,1 }, cnt[SIZE], tp, maxx = 0, ans[SIZE], res = 0;
signed main() {
	io(); cin >> n;
	rep(i, 1, n) {
		cin >> tp;
		cnt[tp]++;
		maxx = max(maxx, tp);
	}
	rep(i, 2, maxx) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	for (int i = maxx; i; --i) {	//求出gcd为i的所有pair的乘积之和
		int s1 = 0, s2 = 0;
		for (int j = i; j <= maxx; j += i) {
			s1 = (s1 + cnt[j] * j % mod) % mod;
			s2 = (s2 + cnt[j] * j % mod * j % mod) % mod;
		}
		ans[i] = (s1 * s1 % mod - s2 + mod) % mod;
		// s1 - s2 的作用是使得gcd为j的pair对数为 cnt * (cnt - 1)
		for (int j = i + i; j <= maxx; j += i) {
			ans[i] = (ans[i] - ans[j] + mod) % mod;
			//去重，删除gcd为ik (k > 1)的pair
		}
	}
	rep(i, 1, maxx) {	//计算 ans[i] / i % mod
		res = (res + ans[i] * inv[i] % mod) % mod;
	}
	cout << res * inv[2] % mod; //res / 2
}
### Prompt

Your challenge is to write a cpp solution to the following problem:

We have an integer sequence of length N: A_0,A_1,\cdots,A_{N-1}.

Find the following sum (\mathrm{lcm}(a, b) denotes the least common multiple of a and b):

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



Since the answer may be enormous, compute it modulo 998244353.

Constraints

* 1 \leq N \leq 200000
* 1 \leq A_i \leq 1000000
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


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


Output

Print the sum modulo 998244353.

Examples

Input

3
2 4 6


Output

22


Input

8
1 2 3 4 6 8 12 12


Output

313


Input

10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644


Output

353891724

### Response

```cpp
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define SIZE 1000100
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define int long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
const int mod = 998244353;
int n, inv[SIZE] = { 0,1 }, cnt[SIZE], tp, maxx = 0, ans[SIZE], res = 0;
signed main() {
	io(); cin >> n;
	rep(i, 1, n) {
		cin >> tp;
		cnt[tp]++;
		maxx = max(maxx, tp);
	}
	rep(i, 2, maxx) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	for (int i = maxx; i; --i) {	//求出gcd为i的所有pair的乘积之和
		int s1 = 0, s2 = 0;
		for (int j = i; j <= maxx; j += i) {
			s1 = (s1 + cnt[j] * j % mod) % mod;
			s2 = (s2 + cnt[j] * j % mod * j % mod) % mod;
		}
		ans[i] = (s1 * s1 % mod - s2 + mod) % mod;
		// s1 - s2 的作用是使得gcd为j的pair对数为 cnt * (cnt - 1)
		for (int j = i + i; j <= maxx; j += i) {
			ans[i] = (ans[i] - ans[j] + mod) % mod;
			//去重，删除gcd为ik (k > 1)的pair
		}
	}
	rep(i, 1, maxx) {	//计算 ans[i] / i % mod
		res = (res + ans[i] * inv[i] % mod) % mod;
	}
	cout << res * inv[2] % mod; //res / 2
}
```