We have an integer sequence of length N: A₀, A, ... A_N−1.

Find the following sum:

$\displaystyle\sum^{N-2}_{i=0}{\sum^{N-1}_{j=i+1}{lcm(Ai, Aj)}}$

(Note: lcm(a, b) denotes the least common multiple of a and b)

Since the answer may be enormous, compute it modulo 998244353

Constraints

• 1 ≤ N ≤ 2 * 10⁵
• 1 ≤ A ≤ 10⁶
• All values in input are integers.

Input

First line of input will be consist of a single N, number of elements.

In next line you will get N space separated integers: A₀ A₁ A₂ A₃ A₄ ... A_N-1

Output

Print the sum modulo 998244353.

Example

Input:
3
2 4 6

Output:
22

Explanation

lcm(2, 4) + lcm(2, 6) + lcm(4, 6) = 4 + 6 + 12 = 22.