← 返回题目列表

Codeforces · 1850/F

F. 我们都是孩子

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

Mihai 和 Slavic 正在观察一群 $$$n$$$ 青蛙,编号从 $$$1$$$ 到 $$$n$$$,最初全部位于 $$$0$$$ 点。 Frog $$$i$$$ 的跳跃长度为 $$$a_i$$$。

每秒,青蛙 $$$i$$$ 向前跳跃 $$$a_i$$$ 个单位。在任何青蛙开始跳跃之前,Slavic 和 Mihai 可以在一个坐标中放置一个陷阱,以便捕获所有将穿过相应坐标的青蛙。

然而,孩子们不能离开家太远,所以他们只能在前 $$$n$$$ 点(即坐标在 $$$1$$$ 和 $$$n$$$ 之间的点)放置陷阱,而孩子们不能在 $$$0$$$ 点放置陷阱,因为他们害怕青蛙。

你能帮助 Slavic 和 Mihai 找出他们用陷阱最多可以捕获多少只青蛙吗?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 青蛙的数量,等于 Slavic 和 Mihai 可以移动放置陷阱的距离。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 相应青蛙的跳跃长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - Slavic 和 Mihai 可以使用陷阱捕获的青蛙的最大数量。

示例

输入 #1

7
5
1 2 3 4 5
3
2 2 2
6
3 1 3 4 9 10
9
1 3 2 4 2 3 7 8 5
1
10
8
7 11 6 8 12 4 4 8
10
9 11 9 12 1 7 2 5 8 10

输出 #1

3
3
3
5
0
4
4

注意

在第一个测试用例中,青蛙将如下跳跃:

- 青蛙 1: $$$0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$$$
- 青蛙 2: $$$0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$$$
- 青蛙 3:$$$0 \到 3 \到 6 \到 9 \到 12 \到 \cdots$$$
- 青蛙 4:$$$0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$$$
- 青蛙 5:$$$0 \到 5 \到 10 \到 15 \到 20 \到 \cdots$$$

在第二个测试用例中,Slavic 和 Mihai 可以在坐标 $$$2$$$ 处放置陷阱并立即捕获所有三只青蛙。