Serval 与音乐游戏

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的严格递增正整数序列 $s_1<s_2<\cdots<s_n$。

对每个 $1\le x\le s_n$，定义 $f(x)$ 为满足下列条件的下标 $i$ 的数量：存在非负整数 $p_i,q_i$，使得

$$s_i=p_i\left\lfloor\frac{s_n}{x}\right\rfloor+q_i\left\lceil\frac{s_n}{x}\right\rceil.$$

求

$$\sum_{x=1}^{s_n}x\cdot f(x)$$

对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试的第一行一个整数 $n$，第二行 $n$ 个严格递增的整数 $s_1,s_2,\ldots,s_n$。

输出格式

对每组测试输出一行一个整数，表示所求答案对 $998244353$ 取模的结果。

样例输入

4
3
1 2 4
4
1 2 7 9
4
344208 591000 4779956 5403429
5
1633 1661 1741 2134 2221

样例输出

26
158
758737625
12334970

数据范围

对所有数据，$1\le t\le10^4$，$1\le n\le10^6$，$1\le s_1<\cdots<s_n\le10^7$。同一输入文件内所有测试的 $n$ 之和不超过 $10^6$，所有测试的 $s_n$ 之和不超过 $10^7$。

子任务编号	分值	特殊限制
1	30	$t\le10,n\le15,s_n\le50$
2		$t\le20,n\le200,s_n\le5000$
3	40	无特殊限制

每个测试点独立计分。