You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Alice和Bob正在观察一群青蛙，编号从$1$到$n$，它们最初都在坐标$0$处。青蛙i可以一次性跳跃$a_i$个单位。

每秒钟，青蛙$i$向前跳跃$a_i$个单位。在青蛙开始跳跃之前，Alice和Bob可以在某个坐标上放置一个陷阱，以便捕捉所有跳到相应坐标的青蛙。

然而，Alice和Bob不能离开家太远，所以他们只能在前$n$个点(即坐标在$1$到$n$之间)放置陷阱，而且他们害怕青蛙，所以不能在坐标$0$处放置陷阱。

你能帮助Alice和Bob找出他们可以使用一个陷阱，最多可以捕捉的青蛙数吗？

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含一个正整数$n$，表示青蛙的数量，也等于Alice和Bob可以放置陷阱的距离。

每个测试用例的第二行包含$n$个以空格分隔的正整数$a_i$，表示对应青蛙的跳跃长度。

输出格式

对于每个测试用例，输出一个整数，表示Alice和Bob使用一个陷阱最多可以捕捉到的青蛙数。

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→⋯

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

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

【数据范围】

对于$20\%$的数据，保证$t\leq100,n\leq 10,1\leq a_i \leq 10^9$。

对于$40\%$的数据，保证$t\leq100,n\leq 10^2,1\leq a_i \leq 10^9$。

对于$60\%$的数据，保证$t\leq100,n\leq 10^3,1\leq a_i \leq 10^9$。

对于$100\%$的数据，保证$t\leq100,n\leq 2\cdot10^5,1\leq a_i \leq 10^9$，同时保证每一个测试点中 $n$的总和不超过 $2\cdot10^5$。