题目背景

此题为 Codeforces Round 886 (Div. 4) 的 F 题，直接去原网站提交即可。

点我跳转原题

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

米哈依和斯拉夫有 $n$ 只青蛙，每只青蛙初始都在 $0$ 位置，每秒会往前跳 $a_{i}$。

你可以在位置 $1$ 到 $n$ 设置一个陷阱，陷阱会抓住经过它的所有青蛙，请问你最多可以抓住几只青蛙。

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) - 青蛙的数量，相当于斯拉夫和米哈伊放置陷阱的距离。

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

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

输出格式

为每个测试用例输出一个整数 - 斯拉维克和米哈伊使用捕捉器能捕捉到的最大青蛙数量。

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$

因此，如果斯拉维奇和米哈伊在坐标 $4$ 处放置一个陷阱，他们可以捕捉到三只青蛙：青蛙 1、青蛙 2 和青蛙 4。可以证明他们再也抓不到其他青蛙了。

在第二个测试案例中，斯拉维奇和米哈伊可以在坐标 $2$ 处放置陷阱，并立即捕获所有三只青蛙。