PRLCM - Personal LCM

We have an integer sequence of length N: A0, A, ... AN−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 * 105
  • 1 ≤ A ≤ 106
  • 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: A0 A1 A2 A3 A4 ... AN-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.


Added by:Amit
Date:2020-06-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-07-13 17:21:53
TLE at case 12
2020-07-11 21:09:32
https://www.quora.com/How-do-I-find-the-sum-of-the-lowest-common-multiples-LCM-of-each-pair-of-integers-from-n-given-positive-integers refer this


Last edit: 2020-07-12 16:22:36
2020-07-09 05:46:27
Is there any editorial about this problem? Can someone share any link?
2020-06-27 11:22:24
is there a faster method to calculate gcd or there is a trick ?????????
2020-06-26 13:28:56
@iseng_cuk It's total running time.
2020-06-26 12:26:42
the time limit is 1s but the accepted solution times are 1.90 and 6.42.
are those numbers in milliseconds?

Author Reply: There are 15 testcases, and for each testcase your program will get 1 sec. So I think you will get 15 sec in total.

oh, I see.

Last edit: 2020-06-28 12:47:45
2020-06-26 02:23:00 [Rampage] Blue.Mary
The input data contains at least one test case with a[i] > 100000; at least one test case with n > 20000. Please check.

Edit: My AC solution assumes n <= 200000 and a[i] <= 1000000.
Reply : Updated.

Last edit: 2020-06-26 05:50:16
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.