F2. Shohag любит считать (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственные различия между двумя версиями этой задачи — ограничения на $$$t$$$, $$$m$$$ и сумму $$$m$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Для массива целых чисел $$$a$$$ длины $$$n$$$ определим $$$f(k)$$$ как наибольший общий делитель (НОД) максимальных значений всех подмассивов$$$^{\text{∗}}$$$ длины $$$k$$$. Например, если массив равен $$$[2, 1, 4, 6, 2]$$$, то $$$f(3) = \operatorname{gcd}(\operatorname{max}([2, 1, 4]), \operatorname{max}([1, 4, 6]), \operatorname{max}([4, 6, 2])) = \operatorname{gcd}(4, 6, 6) = 2$$$.

Массив является хорошим, если для всех пар $$$1 \le i \lt j \le n$$$ выполняется $$$f(i) \neq f(j)$$$.

У Shohag есть целое число $$$m$$$. Помогите ему подсчитать количество непустых хороших массивов произвольной длины, каждый элемент которых является целым числом от $$$1$$$ до $$$m$$$, по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Массив $$$d$$$ является подмассивом массива $$$c$$$, если $$$d$$$ можно получить из $$$c$$$ путем удаления нескольких (возможно, нуля или всех) элементов из начала и нескольких (возможно, нуля или всех) элементов из конца.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит целое число $$$m$$$ ($$$1 \le m \le 10^6$$$).

Обратите внимание, что сумма $$$m$$$ по всем наборам входных данных не ограничена.

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

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

Пример
Входные данные
3
2
5
9
Выходные данные
4
29
165
Примечание

В первом наборе входных данных подходящими массивами являются $$$[1]$$$, $$$[1, 2]$$$, $$$[2]$$$ и $$$[2, 1]$$$.

Во втором наборе входных данных всего $$$29$$$ подходящих массивов. В частности, массив $$$[2, 1, 4]$$$ длины $$$n = 3$$$ подходит, так как все его элементы принадлежат отрезку от $$$1$$$ до $$$m = 5$$$ и $$$f(1)$$$, $$$f(2)$$$ и $$$f(n = 3)$$$ различны:

  • $$$f(1) = \operatorname{gcd}(\operatorname{max}([2]), \operatorname{max}([1]), \operatorname{max}([4])) = \operatorname{gcd}(2, 1, 4) = 1.$$$
  • $$$f(2) = \operatorname{gcd}(\operatorname{max}([2, 1]), \operatorname{max}([1, 4])) = \operatorname{gcd}(2, 4) = 2.$$$
  • $$$f(3) = \operatorname{gcd}(\operatorname{max}([2, 1, 4])) = \operatorname{gcd}(4) = 4.$$$