This is the hard version of the problem. The only differences between the two versions of this problem are the constraints on $t$, $m$, and the sum of $m$. You can only make hacks if both versions of the problem are solved.

For an integer array $a$ of length $n$, define $f(k)$ as the greatest common divisor (GCD) of the maximum values of all subarrays$^{\text{∗}}$ of length $k$. For example, if the array is $[2, 1, 4, 6, 2]$, then $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$.

An array is good if $f(i) \neq f(j)$ is satisfied over all pairs $1 \le i \lt j \le n$.

Shohag has an integer $m$. Help him count the number, modulo $998\,244\,353$, of non-empty good arrays of arbitrary length such that each element of the array is an integer from $1$ to $m$.

$^{\text{∗}}$An array $d$ is a subarray of an array $c$ if $d$ can be obtained from $c$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains a single integer $t$ ($1 \le t \le 3 \cdot 10^5$) — the number of test cases.

The first and only line of each test case contains an integer $m$ ($1 \le m \le 10^6$).

Note that there is no limit on the sum of $m$ over all test cases.

Output

For each test case, output an integer — the number of valid arrays modulo $998\,244\,353$.

Note

In the first test case, the valid arrays are $[1]$, $[1, 2]$, $[2]$, and $[2, 1]$.

In the second test case, there are a total of $29$ valid arrays. In particular, the array $[2, 1, 4]$ with length $n = 3$ is valid because all elements are from $1$ to $m = 5$ and $f(1)$, $f(2)$ and $f(n = 3)$ all are distinct:

• $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.$