杂题——We Were Both Children

We Were Both Children

Mihai and Slavic were looking at a group of $n$ frogs, numbered from $1$ to $n$, all initially located at point $0$. Frog $i$ has a hop length of $a_i$.

Each second, frog $i$ hops $a_i$ units forward. Before any frogs start hopping, Slavic and Mihai can place exactly one trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate.

However, the children can’t go far away from their home so they can only place a trap in the first $n$ points (that is, in a point with a coordinate between $1$ and $n$) and the children can’t place a trap in point $0$ since they are scared of frogs.

Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.

The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the lengths of the hops of the corresponding frogs.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.

  • *

Output

For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

output

1
2
3
4
5
6
7
3
3
3
5
0
4
4

Note

In the first test case, the frogs will hop as follows:

  • Frog 1: $0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$
  • Frog 2: $0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$
  • Frog 3: $0 \to 3 \to 6 \to 9 \to 12 \to \cdots$
  • Frog 4: $0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$
  • Frog 5: $0 \to 5 \to 10 \to 15 \to 20 \to \cdots$

Therefore, if Slavic and Mihai put a trap at coordinate $4$, they can catch three frogs: frogs 1, 2, and 4. It can be proven that they can’t catch any more frogs.

In the second test case, Slavic and Mihai can put a trap at coordinate $2$ and catch all three frogs instantly.

翻译

Mihai 和 Slavic 正在观察一群 $n$ 青蛙，编号从 $1$ 到 $n$ ，最初全部位于点 $0$ 。青蛙 $i$ 的跳跃长度为 $a _ i$ 。

每秒，青蛙 $i$ 向前跳跃 $a _ i$ 个单位。在任何青蛙开始跳跃之前，Slavic 和 Mihai 可以在某个坐标中放置一个陷阱，以便捕获所有将穿过相应坐标的青蛙。

但孩子们不能离开家太远，只能在前面的 $n$ 点(即坐标在 $1$ 到 $n$ 之间的点)放置陷阱，孩子们可以不要在点 $0$ 放置陷阱，因为它们害怕青蛙。

你能帮助斯拉夫和米哈伊找出他们用陷阱最多能捕获多少只青蛙吗？

输入

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

每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — 青蛙的数量，等于 Slavic 和 Mihai 可以移动以放置陷阱的距离。

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

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

输出

对于每个测试用例，输出一个整数 - Slavic 和 Mihai 使用陷阱可以捕获的青蛙的最大数量。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

output

1
2
3
4
5
6
7
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$ 处放置陷阱并立即捕获所有三只青蛙。

思路

​ 我们可以记录每只青蛙可以跳到的所有位置,最后再找到这些位置中跳到青蛙数量最多的位置即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;

void solve() {
    int n;cin >> n;
    vector<ll>step(n+1);
    vector<ll>cnt(n+1);

    for(int i = 0;i < n;i++){
        int x;cin >> x;
        if(x <= n)step[x]++;    //记录一步走x格的数量
    }

    for(int i = 1;i <= n;i++){  //枚举所有走多少格的情况
        for(int j = i;j <= n;j+=i){ //枚举走i格的时候，在前n格内，能够走到的所有格
            cnt[j] += step[i];   //第j格可以有step[i]个青蛙走过
        }
    }

    cout << *max_element(cnt.begin(),cnt.end()) << ed;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}