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

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

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

$1\leq t\leq 3\times 10^5,1\leq m\leq 10^6.$ **注意 $\sum m$ 没有限制。**