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

Shohag Loves Counting (Hard Version)

Examples