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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        static final int MODULO = 998244353;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n];
            int max = 2;
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
                max = Math.max(max, a[i] + 1);
            }
            int[] sum = new int[max];
            for (int x : a) {
                sum[x] += x;
                if (sum[x] >= MODULO) sum[x] -= MODULO;
            }
            boolean[] prime = new boolean[max];
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            for (int i = 2; i * i < max; ++i)
                if (prime[i]) {
                    for (int j = i * i; j < max; j += i) prime[j] = false;
                }
            int[] ps = new int[max];
            int nps = 0;
            for (int i = 2; i < max; ++i) if (prime[i]) ps[nps++] = i;
            ps = Arrays.copyOf(ps, nps);
            for (int p : ps) {
                for (int i = (max - 1) / p; i >= 1; --i) {
                    sum[i] += sum[i * p];
                    if (sum[i] >= MODULO) sum[i] -= MODULO;
                }
            }
            for (int i = 0; i < max; ++i) sum[i] = (int) (sum[i] * (long) sum[i] % MODULO);
            for (int p : ps) {
                int upto = (max - 1) / p;
                for (int i = 1; i <= upto; ++i) {
                    sum[i] -= sum[i * p];
                    if (sum[i] < 0) sum[i] += MODULO;
                }
            }
            int[] invs = new int[max];
            invs[1] = 1;
            for (int i = 2; i < invs.length; ++i) {
                invs[i] = (int) ((MODULO - invs[((int) (MODULO % i))] * (long) (MODULO / i) % MODULO) % MODULO);
                if (invs[i] * (long) i % MODULO != 1) throw new RuntimeException();
            }
            long res = 0;
            for (int i = 1; i < max; ++i) {
                res += sum[i] * (long) invs[i] % MODULO;
            }
            for (int x : a) {
                res -= x;
            }
            res %= MODULO;
            res += MODULO;
            res %= MODULO;
            res *= invs[2];
            res %= MODULO;
            out.println(res);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

