Shohag Loves Counting (Hard Version)
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3200
Tags: dp, number theory

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

Input format:
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 format:
For each test case, output an integer — the number of valid arrays modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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

Example input:
3
2
5
9

Example output:
4
29
165

Editorial:
First, check the editorial of F1.
Note that for F2 there is no limit on the sum of $$$m$$$, so we need to change the approach a bit.
And for F2 you need to remove the length from the dp state (which I described at the end of the editorial of F1).
Now instead of iterating $$$i$$$ from $$$m$$$ to $$$1$$$, we iterate from $$$1$$$ to $$$m$$$. And reformulate the dp as follows.
Let's say we are building the strictly increasing sequence $$$a$$$ from left to right and we are fixing what the suffix GCD of the final array $$$a$$$ starting from each element will be.
Let $$$\text{dp}_{j, h}$$$ be the sum of $$$2^{\text{length of array so far} - 1}$$$ for all $$$a$$$ such that we are at element $$$j$$$ and the suffix GCD of the final array $$$a$$$ starting from element $$$j$$$ is $$$h$$$.
Then the transition is to iterate over the previous suffix GCD $$$g$$$ at element $$$i$$$ such that $$$g$$$ divides $$$h$$$, $$$g < h$$$ and $$$g = \text{gcd}(i, h)$$$ and then add $$$\text{dp}_{i, g}$$$ to $$$\text{dp}_{j, h}$$$.
Just like F1, we can speed up the transitions by tracking some prefix sums and doing inclusion-exclusion on the divisors of $$$i$$$. We can use the Mobius Inversion Formula to do it in $$$O(\sum_{d | i} \sigma(d))$$$. Another way to make it faster is to do SOS DP on the divisors of $$$i$$$ which will take $$$O(\sigma(i) \cdot p(i))$$$ where $$$p(i)$$$ is the number of unique prime factors of $$$i$$$.
It is hard to describe all the little details of the implementation here, please refer to the code for more details.
The overall time complexity is $$$O(\sum_{i = 1}^M \sigma(i) \cdot p(i))$$$ or $$$O(\sum_{i = 1}^M \sum_{d | i} \sigma(d))$$$ where $$$M$$$ is the maximum value of $$$m$$$. Both work fast enough.