题目描述

Mihai 和 Slavic 正在观察一群编号为 $1$ 到 $n$ 的青蛙，这些青蛙最初都位于坐标 $0$。第 $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 \times 10^5$），表示青蛙的数量，也等于 Slavic 和 Mihai 能够放置陷阱的最远距离。

每个测试用例的第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每只青蛙的跳跃距离。

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

输出格式

对于每个测试用例，输出一个整数，表示 Slavic 和 Mihai 使用一个陷阱最多能捕捉到的青蛙数量。

样例

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

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 \to 3 \to 6 \to 9 \to 12 \to \cdots$
• 青蛙 4：$0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$
• 青蛙 5：$0 \to 5 \to 10 \to 15 \to 20 \to \cdots$

因此，如果 Slavic 和 Mihai 在坐标 $4$ 处放置陷阱，他们可以捕捉到三只青蛙：青蛙 1、2 和 4。可以证明他们无法捕捉更多的青蛙。

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

由 ChatGPT 4.1 翻译

来源

Codeforces 1850F，英文题名 We Were Both Children。