F2. Shohag Loves Counting (Hard Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

Example
Input
3
2
5
9
Output
4
29
165
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.$$$