题目描述

熊大和熊二正在观察一群青蛙，这些青蛙从 $1$ 到 $n$ 编号，初始都位于坐标 0。青蛙 $i$ 的跳跃长度为 $a_i$。

每秒，青蛙 $i$ 都会向前跳 $a_i$ 个单位。在任何青蛙开始跳跃之前，熊大和熊二可以在一个坐标上放置一只陷阱，以捕捉所有将通过相应坐标的青蛙。

然而，二熊不能离开家太远，所以他们只能在前 $n$ 个点（即坐标在 $1$ 到 $n$ 之间的点）放置陷阱，而且二熊不能在坐标 0 的点上放置陷阱，因为他们害怕青蛙。

你能帮助熊大和熊二找出使用一个陷阱能够捕捉到的最大青蛙数量吗？

输入格式

输入的第一行包含一个整数 $t(1≤t≤100)$ ——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n(1≤n≤2×10^5)$ ——青蛙的数量，这等于熊大和熊二可以行走以放置陷阱的距离。

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

保证所有测试用例中 $n$ 的总和不超过 $2×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→1→2→3→4→⋯$

青蛙 2：$0→2→4→6→8→⋯$

青蛙 3：$0→3→6→9→12→⋯$

青蛙 4：$0→4→8→12→16→⋯$

青蛙 5：$0→5→10→15→20→⋯$

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

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