← 返回题目列表

Codeforces · 2039/F1

F1. Shohag 喜欢计数(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。该问题的两个版本之间的唯一区别是对 $$$t$$$、$$$m$$$ 和 $$$m$$$ 总和的约束。只有解决了两个版本的问题后,您才能进行黑客攻击。

对于长度为 $$$n$$$ 的整数数组 $$$a$$$,将 $$$f(k)$$$ 定义为长度为 $$$k$$$ 的所有子数组 $$$^{\text{∗}}$$$ 的最大值的最大公约数 (GCD)。例如,如果数组为 $$$[2, 1, 4, 6, 2]$$$,则 $$$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$$$。

如果 $$$f(i) \neq f(j)$$$ 对所有对 $$$1 \le i \lt j \le n$$$ 都满足,则数组是好的。

Shohag 有一个整数 $$$m$$$。帮助他计算任意长度的非空好数组的数量,以 $$$998\,244\,353$$$ 为模,使得数组的每个元素都是从 $$$1$$$ 到 $$$m$$$ 的整数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$)。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 有效数组的数量以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3
2
5
9

输出 #1

4
29
165

注意

在第一个测试用例中,有效数组为 $$$[1]$$$、$$$[1, 2]$$$、$$$[2]$$$ 和 $$$[2, 1]$$$。

在第二个测试用例中,总共有 $$$29$$$ 有效数组。特别是,长度为 $$$n = 3$$$ 的数组 $$$[2, 1, 4]$$$ 是有效的,因为所有元素从 $$$1$$$ 到 $$$m = 5$$$ 且 $$$f(1)$$$、$$$f(2)$$$ 和 $$$f(n = 3)$$$ 都是不同的:

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