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