CF1789E.Serval and Music Game

Serval loves playing music games. He meets a problem when playing music games, and he leaves it for you to solve.

You are given $n$ positive integers $s_1 \lt s_2 \lt \ldots \lt s_n$. $f(x)$ is defined as the number of $i$ ($1\leq i\leq n$) that exist non-negative integers $p_i, q_i$ such that:

$$s\_i=p\_i\\left\\lfloor{s\_n\\over x}\\right\\rfloor + q\_i\\left\\lceil{s\_n\\over x}\\right\\rceil$$

Find out $\sum_{x=1}^{s_n} x\cdot f(x)$ modulo $998\,244\,353$.

As a reminder, $\lfloor x\rfloor$ denotes the maximal integer that is no greater than $x$, and $\lceil x\rceil$ denotes the minimal integer that is no less than $x$.

小猫塞尔瓦喜欢玩音乐游戏。他在玩音乐游戏时遇到了一个问题，现在交由你来解决。

给定 $n$ 个正整数 $s_1 \lt s_2 \lt \ldots \lt s_n$。定义函数 $f(x)$ 为满足如下条件的下标 $i$（其中 $1\leq i\leq n$）的个数：存在非负整数 $p_i, q_i$，使得

$$s\_i=p\_i\\left\\lfloor{s\_n\\over x}\\right\\rfloor + q\_i\\left\\lceil{s\_n\\over x}\\right\\rceil$$

请计算 $\sum_{x=1}^{s_n} x\cdot f(x)$ 对 $998\,244\,353$ 取模的结果。

提示：$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数（即向下取整），$\lceil x\rceil$ 表示不小于 $x$ 的最小整数（即向上取整）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 10^4$). The description of the test cases follows.

The first line of each test cases contains a single integer $n$ ($1\leq n\leq 10^6$).

The second line of each test case contains $n$ positive integers $s_1,s_2,\ldots,s_n$ ($1\leq s_1 \lt s_2 \lt \ldots \lt s_n \leq 10^7$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$, and the sum of $s_n$ does not exceed $10^7$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1\leq t\leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 10^6$）。

每个测试用例的第二行包含 $n$ 个正整数 $s_1,s_2,\ldots,s_n$（$1\leq s_1 \lt s_2 \lt \ldots \lt s_n \leq 10^7$）。

保证所有测试用例的 $n$ 之和不超过 $10^6$，且所有测试用例的 $s_n$ 之和不超过 $10^7$。

For each test case, print a single integer in a single line — the sum of $x\cdot f(x)$ over all possible $x$ modulo $998\,244\,353$.

对于每个测试用例，在一行中输出一个整数——对所有可能的 $x$，求 $x\cdot f(x)$ 的和，并对 $998\,244\,353$ 取模。

For the first test case, $s_n=4$, $f(x)$ are calculated as followings:

• $f(1)=1$
  • $\left\lfloor s_n\over 1\right\rfloor=4$, $\left\lceil s_n\over 1\right\rceil=4$.
  • It can be shown that such $p_1,p_2$ and $q_1,q_2$ that satisfy the conditions don't exist.
  • Let $p_3=1$ and $q_3=0$, then $s_3 = p_3\cdot\left\lfloor s_n\over 1\right\rfloor + q_3\cdot\left\lceil s_n\over 1\right\rceil = 1\cdot 4 + 0\cdot 4 = 4$.
• $f(2)=2$
  • $\left\lfloor s_n\over 2\right\rfloor=2$, $\left\lceil s_n\over 2\right\rceil=2$.
  • It can be shown that such $p_1$ and $q_1$ that satisfy the conditions don't exist.
  • Let $p_2=1$ and $q_2=0$, then $s_2 = p_2\cdot\left\lfloor s_n\over 2\right\rfloor + q_2\cdot\left\lceil s_n\over 2\right\rceil = 1\cdot 2 + 0\cdot 2 = 2$.
  • Let $p_3=0$ and $q_3=2$, then $s_3 = p_3\cdot\left\lfloor s_n\over 2\right\rfloor + q_3\cdot\left\lceil s_n\over 2\right\rceil = 0\cdot 2 + 2\cdot 2 = 4$.
• $f(3)=3$
  • $\left\lfloor s_n\over 3\right\rfloor=1$, $\left\lceil s_n\over 3\right\rceil=2$.
  • Let $p_1=1$ and $q_1=0$, then $s_1 = p_1\cdot\left\lfloor s_n\over 3\right\rfloor + q_1\cdot\left\lceil s_n\over 3\right\rceil = 1\cdot 1 + 0\cdot 2 = 1$.
  • Let $p_2=0$ and $q_2=1$, then $s_2 = p_2\cdot\left\lfloor s_n\over 3\right\rfloor + q_2\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 1\cdot 2 = 2$.
  • Let $p_3=0$ and $q_3=2$, then $s_3 = p_3\cdot\left\lfloor s_n\over 3\right\rfloor + q_3\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 2\cdot 2 = 4$.
• $f(4)=3$
  • $\left\lfloor s_n\over 4\right\rfloor=1$, $\left\lceil s_n\over 4\right\rceil=1$.
  • Let $p_1=1$ and $q_1=0$, then $s_1 = p_1\cdot\left\lfloor s_n\over 4\right\rfloor + q_1\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 0\cdot 1 = 1$.
  • Let $p_2=1$ and $q_2=1$, then $s_2 = p_2\cdot\left\lfloor s_n\over 4\right\rfloor + q_2\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 1\cdot 1 = 2$.
  • Let $p_3=2$ and $q_3=2$, then $s_3 = p_3\cdot\left\lfloor s_n\over 4\right\rfloor + q_3\cdot\left\lceil s_n\over 4\right\rceil = 2\cdot 1 + 2\cdot 1 = 4$.

Therefore, the answer is $\sum_{x=1}^4 x\cdot f(x) = 1\cdot 1 + 2\cdot 2 + 3\cdot 3 + 4\cdot 3 = 26$.

For the second test case:

• $f(1)=f(2)=f(3)=1$
• $f(4)=3$
• $f(5)=f(6)=f(7)=f(8)=f(9)=4$

For example, when $x=3$ we have $f(3)=1$ because there exist $p_4$ and $q_4$:

$$9 = 1 \\cdot\\left\\lfloor{9\\over 3}\\right\\rfloor + 2 \\cdot\\left\\lceil{9\\over 3}\\right\\rceil$$

It can be shown that it is impossible to find $p_1,p_2,p_3$ and $q_1,q_2,q_3$ that satisfy the conditions.

When $x=5$ we have $f(5)=4$ because there exist $p_i$ and $q_i$ as followings:

1 = 1 \\cdot\\left\\lfloor{9\\over 5}\\right\\rfloor + 0 \\cdot\\left\\lceil{9\\over 5}\\right\\rceil$$ $$2 = 0 \\cdot\\left\\lfloor{9\\over 5}\\right\\rfloor + 1 \\cdot\\left\\lceil{9\\over 5}\\right\\rceil$$ $$7 = 3 \\cdot\\left\\lfloor{9\\over 5}\\right\\rfloor + 2 \\cdot\\left\\lceil{9\\over 5}\\right\\rceil$$ $$9 = 3 \\cdot\\left\\lfloor{9\\over 5}\\right\\rfloor + 3 \\cdot\\left\\lceil{9\\over 5}\\right\\rceil

Therefore, the answer is $\sum_{x=1}^9 x\cdot f(x) = 158$.

对于第一个测试用例，$s_n=4$，函数 $f(x)$ 的计算过程如下：

• $f(1)=1$
  • $\left\lfloor s_n\over 1\right\rfloor=4$，$\left\lceil s_n\over 1\right\rceil=4$。
  • 可以证明，不存在满足条件的 $p_1,p_2$ 和 $q_1,q_2$。
  • 令 $p_3=1$、$q_3=0$，则 $s_3 = p_3\cdot\left\lfloor s_n\over 1\right\rfloor + q_3\cdot\left\lceil s_n\over 1\right\rceil = 1\cdot 4 + 0\cdot 4 = 4$。
• $f(2)=2$
  • $\left\lfloor s_n\over 2\right\rfloor=2$，$\left\lceil s_n\over 2\right\rceil=2$。
  • 可以证明，不存在满足条件的 $p_1$ 和 $q_1$。
  • 令 $p_2=1$、$q_2=0$，则 $s_2 = p_2\cdot\left\lfloor s_n\over 2\right\rfloor + q_2\cdot\left\lceil s_n\over 2\right\rceil = 1\cdot 2 + 0\cdot 2 = 2$。
  • 令 $p_3=0$、$q_3=2$，则 $s_3 = p_3\cdot\left\lfloor s_n\over 2\right\rfloor + q_3\cdot\left\lceil s_n\over 2\right\rceil = 0\cdot 2 + 2\cdot 2 = 4$。
• $f(3)=3$
  • $\left\lfloor s_n\over 3\right\rfloor=1$，$\left\lceil s_n\over 3\right\rceil=2$。
  • 令 $p_1=1$、$q_1=0$，则 $s_1 = p_1\cdot\left\lfloor s_n\over 3\right\rfloor + q_1\cdot\left\lceil s_n\over 3\right\rceil = 1\cdot 1 + 0\cdot 2 = 1$。
  • 令 $p_2=0$、$q_2=1$，则 $s_2 = p_2\cdot\left\lfloor s_n\over 3\right\rfloor + q_2\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 1\cdot 2 = 2$。
  • 令 $p_3=0$、$q_3=2$，则 $s_3 = p_3\cdot\left\lfloor s_n\over 3\right\rfloor + q_3\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 2\cdot 2 = 4$。
• $f(4)=3$
  • $\left\lfloor s_n\over 4\right\rfloor=1$，$\left\lceil s_n\over 4\right\rceil=1$。
  • 令 $p_1=1$、$q_1=0$，则 $s_1 = p_1\cdot\left\lfloor s_n\over 4\right\rfloor + q_1\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 0\cdot 1 = 1$。
  • 令 $p_2=1$、$q_2=1$，则 $s_2 = p_2\cdot\left\lfloor s_n\over 4\right\rfloor + q_2\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 1\cdot 1 = 2$。
  • 令 $p_3=2$、$q_3=2$，则 $s_3 = p_3\cdot\left\lfloor s_n\over 4\right\rfloor + q_3\cdot\left\lceil s_n\over 4\right\rceil = 2\cdot 1 + 2\cdot 1 = 4$。

因此，答案为 $\sum_{x=1}^4 x\cdot f(x) = 1\cdot 1 + 2\cdot 2 + 3\cdot 3 + 4\cdot 3 = 26$。

对于第二个测试用例：

• $f(1)=f(2)=f(3)=1$
• $f(4)=3$
• $f(5)=f(6)=f(7)=f(8)=f(9)=4$

例如，当 $x=3$ 时，有 $f(3)=1$，因为存在 $p_4$ 和 $q_4$ 满足：

$$9 = 1 \cdot\left\lfloor{9\over 3}\right\rfloor + 2 \cdot\left\lceil{9\over 3}\right\rceil$$

可以证明，不存在满足条件的 $p_1,p_2,p_3$ 和 $q_1,q_2,q_3$。

当 $x=5$ 时，有 $f(5)=4$，因为存在如下 $p_i$ 和 $q_i$：

1 = 1 \cdot\left\lfloor{9\over 5}\right\rfloor + 0 \cdot\left\lceil{9\over 5}\right\rceil$$ $$2 = 0 \cdot\left\lfloor{9\over 5}\right\rfloor + 1 \cdot\left\lceil{9\over 5}\right\rceil$$ $$7 = 3 \cdot\left\lfloor{9\over 5}\right\rfloor + 2 \cdot\left\lceil{9\over 5}\right\rceil$$ $$9 = 3 \cdot\left\lfloor{9\over 5}\right\rfloor + 3 \cdot\left\lceil{9\over 5}\right\rceil

因此，答案为 $\sum_{x=1}^9 x\cdot f(x) = 158$。