F2. Shohag 喜欢计数（困难版）

时间限制： 每个测试点 $4$ 秒
内存限制： 每个测试点 $512$ 兆字节

这是本题的困难版本。两个版本之间的唯一区别在于 $t$、$m$ 以及 $m$ 的总和的范围不同。只有当你解决了本题的两个版本时，才能进行$hack$。

---

对于长度为 $n$ 的整数数组 $a$，定义 $f(k)$ 为所有长度为 $k$ 的子数组的最大值的最大公约数（GCD）。
例如，若数组为 $[2,1,4,6,2]$，则

$$f(3) = \gcd\big(\max([2,1,4]),\ \max([1,4,6]),\ \max([4,6,2])\big) = \gcd(4,6,6) = 2. $$

如果一个数组满足：对于所有 $1 \le i < j \le n$ 都有 $f(i) \neq f(j)$，则称这个数组是好的。

Shohag 有一个整数 $m$。
请帮他计算：有多少个非空的好数组，其长度任意，且数组中的每个元素都是 $1$ 到 $m$ 之间的整数？
答案对 $998244353$ 取模。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 3 \times 10^5$）—— 测试用例的数量。
接下来每个测试用例包含一行，每行有一个整数 $m$（$1 \le m \le 10^6$）。

注意：所有测试用例的 $m$ 之和没有限制。

---

输出格式

对于每个测试用例，输出一个整数 —— 符合条件的数组数量，对 $998244353$ 取模。

---

示例

输入：

3
2
5
9

输出：

4
29
165

---

示例解释

在第一个测试用例（$m=2$）中，符合条件的数组有：
$[1]$, $[1,2]$, $[2]$, $[2,1]$。

在第二个测试用例（$m=5$）中，共有 $29$ 个符合条件的数组。
例如，数组 $[2,1,4]$（长度为 $3$）是符合条件的，因为所有元素都在 $1$ 到 $5$ 之间，且 $f(1)$、$f(2)$ 和 $f(3)$ 互不相同：

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

---