CF2039F2 Shohag Loves Counting (Hard Version)

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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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]), \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. $