Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

We all know that Chef got a box of $N$ chocolates (numbered $1$ through $N$) as his birthday present. For each valid $i$, the $i$-th chocolate has a sweetness value $W_{i}$. Chef is going to play the following randomised game for fun with his brother:
First, an integer $k$ between $1$ and $N$ (inclusive) is chosen uniformly randomly.
Then, $k$ times, Chef chooses a chocolate from the box uniformly randomly and independently (each chocolate may be chosen multiple times). For each $i$ ($1 ≤ i ≤ k$), let's denote the sweetness of the $i$-th chocolate chosen by Chef by $A_{i}$.
Chef's brother does the same thing ― $k$ times, he also chooses a chocolate from the box uniformly randomly and independently from each other or Chef's choices (so each chocolate may still be chosen multiple times). For each $i$ ($1 ≤ i ≤ k$), let's denote the sweetness of the $i$-th chocolate chosen by Chef's brother by $B_{i}$.
The score of the game is $\sum_{i=1}^k \sum_{j=1}^k \mathrm{gcd}(A_{i}, B_{j})$.

Find the expected value of the score. It can be proved that this expected value can be expressed as a fraction $\frac{P}{Q}$, where $P$ and $Q$ are positive integers and $Q$ is coprime with $998,244,353$. You should compute $P \cdot Q^{-1}$ modulo $998,244,353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $998,244,353$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $W_{1}, W_{2}, \ldots, W_{N}$.

------  Output ------
For each test case, print a single line containing one integer $P \cdot Q^{-1}$ modulo $998,244,353$.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤ W_{i} ≤ 5 \cdot 10^{5}$ for each valid $i$

----- Sample Input 1 ------ 
2

3

1 2 3

4

2 2 2 2
----- Sample Output 1 ------ 
887328320

15
----- explanation 1 ------ 
Example case 2:
- When $k = 1$, the score is $1^{2} \cdot 2 = 2$.
- When $k = 2$, the score is $2^{2} \cdot 2 = 8$.
- When $k = 3$, the score is $3^{2} \cdot 2 = 18$.
- When $k = 4$, the score is $4^{2} \cdot 2 = 32$.

The expected score is $\frac{2+8+18+32}{4} = 15$.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Probability

Starter code:

Solutions:
mod = 998244353

def power(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	temp = power(a, int(b / 2)) % mod
	if b % 2 == 0:
		return temp % mod * (temp % mod) % mod
	else:
		return temp % mod * (a % mod) % mod * (temp % mod) % mod
MaxW = 500005

def comp_exp_gcd(w, n):
	c = [0] * (MaxW + 1)
	d = [0] * (MaxW + 1)
	e = [0] * (MaxW + 1)
	for i in w:
		c[i] += 1
	for i in range(1, MaxW + 1):
		for j in range(2 * i, MaxW + 1, i):
			c[i] += c[j]
	ans = 0
	for i in range(MaxW, 0, -1):
		d[i] = c[i] * c[i]
		for j in range(2 * i, MaxW + 1, i):
			d[i] -= d[j]
		ans = (ans + i * d[i]) % mod
	inv = power(n, mod - 2) % mod
	print(ans * (n + 1) % mod * (2 * n + 1) % mod * power(6, mod - 2) % mod * inv * inv % mod)
t = int(input())
while t > 0:
	n = int(input())
	str = input().split(' ')
	w = []
	for i in str:
		w.append(int(i))
	exp_gcd = comp_exp_gcd(w, n)
	t -= 1