CF1850F We Were Both Children

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 使用一个陷阱最多能捕捉到的青蛙数量。

在第一个测试用例中，青蛙的跳跃如下： - 青蛙 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 翻译