CF2039F2.Shohag Loves Counting (Hard Version)

此题为困难版本。简单版本和困难版本的区别在于 $t,m,\sum m$ 的数据范围。

对于一个包含 $n$ 个元素的数组 $a$，定义 $f(k)$ 表示数组 $a$ 所有长度为 $k$ 的子串的最大值的最大公因数。

例如，对于数组 $[2,1,4,6,2]$，$f(3)=\gcd(\max(2,1,4),\max(1,4,6),\max(4,6,2))=\gcd(4,6,6)=2$。

定义一个数组 $a$ 是好的，当且仅当 $\forall 1\leq i<j\leq n，f(i)\neq f(j)$。现在，给定一个数 $m$，请你算出任意非空的仅包含 $1$ 到 $m$ 内的所有整数的好的数组有多少个。由于这样的数组可能很多，答案请对 $998244353$ 取模。

例如，当 $m=2$ 时，所有满足上述要求的数组有 $[1],[1,2],[2],[2,1]$。

第一行一个整数 $t$ 代表数据组数。

接下来 $t$ 行，每行一个整数 $m$，代表一组数据。

$t$ 行，每行一个整数，代表每组询问的答案模 $998244353$ 的结果。

$1\leq t\leq 3\times 10^5,1\leq m\leq 10^6.$

注意 $\sum m$ 没有限制。