Serval and Music Game

Description:

Input:

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 < s_2 < \ldots < 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$$$.

Output:

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$$$.

Sample Input:

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

Sample Output:

26
158
758737625
12334970

Note:

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$$$.