#include <cstdio>
#include <iostream>
#define mod 998244353
using namespace std;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int n, a[200005], mx;
long long ans, f[1000006], g[1000006];
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        mx = max(a[i] = read(), mx);
        for (int j = 1; j * j <= a[i]; j++)
            if (a[i] % j == 0) {
                g[j] += a[i] / j;
                if (j * j != a[i]) g[a[i] / j] += j;
            }
    }
    for (int i = 1; i <= mx; i++)
        g[i] %= mod, f[i] = g[i] * g[i] % mod * i % mod;
    for (int i = mx; i; i--) {
        for (int j = 2; i * j <= mx; j++)
            f[i] = (f[i] - f[i * j] * j % mod + mod) % mod;
        ans += f[i];
    }
    ans %= mod;
    for (int i = 1; i <= n; ++i) (ans += mod - a[i]) %= mod;

    printf("%lld\n", ans * 499122177 % mod);
    return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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
#include <cstdio>
#include <iostream>
#define mod 998244353
using namespace std;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int n, a[200005], mx;
long long ans, f[1000006], g[1000006];
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        mx = max(a[i] = read(), mx);
        for (int j = 1; j * j <= a[i]; j++)
            if (a[i] % j == 0) {
                g[j] += a[i] / j;
                if (j * j != a[i]) g[a[i] / j] += j;
            }
    }
    for (int i = 1; i <= mx; i++)
        g[i] %= mod, f[i] = g[i] * g[i] % mod * i % mod;
    for (int i = mx; i; i--) {
        for (int j = 2; i * j <= mx; j++)
            f[i] = (f[i] - f[i * j] * j % mod + mod) % mod;
        ans += f[i];
    }
    ans %= mod;
    for (int i = 1; i <= n; ++i) (ans += mod - a[i]) %= mod;

    printf("%lld\n", ans * 499122177 % mod);
    return 0;
}
```