E. Serval и музыкальная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Serval любит играть в музыкальные игры. Он столкнулся с проблемой, играя в музыкальные игры, и оставил её решать вам.

Вам даны $$$n$$$ положительных целых чисел $$$s_1 < s_2 < \ldots < 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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит количество наборов входных данных $$$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 < s_2 < \ldots < s_n \leq 10^7$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$, и сумма $$$s_n$$$ по всем наборам входных данных не превосходит $$$10^7$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — сумму $$$x\cdot f(x)$$$ по всем возможным $$$x$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$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$$$.