Mihai 和 Slavic 正在观察一群 $$$n$$$ 青蛙,编号从 $$$1$$$ 到 $$$n$$$,最初全部位于 $$$0$$$ 点。 Frog $$$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 \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 可以使用陷阱捕获的青蛙的最大数量。
示例
输入 #1
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
输出 #1
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 \到 3 \到 6 \到 9 \到 12 \到 \cdots$$$
- 青蛙 4:$$$0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$$$
- 青蛙 5:$$$0 \到 5 \到 10 \到 15 \到 20 \到 \cdots$$$
在第二个测试用例中,Slavic 和 Mihai 可以在坐标 $$$2$$$ 处放置陷阱并立即捕获所有三只青蛙。