F. We Were Both Children
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Михай и Славик смотрели на группу из $$$n$$$ лягушек, пронумерованных от $$$1$$$ до $$$n$$$, которые изначально находились в точке $$$0$$$. Лягушка $$$i$$$ может прыгнуть на расстояние $$$a_i$$$.

Каждую секунду лягушка $$$i$$$ прыгает на $$$a_i$$$ единиц вперед. Прежде чем лягушки начнут прыгать, Славик и Михай могут поставить ровно одну ловушку в координате, чтобы поймать всех лягушек, которые когда-либо пройдут через эту координату.

Однако, дети не могут уйти далеко от своего дома, поэтому они могут поставить ловушку только в одной из первых $$$n$$$ точках (то есть в точке с координатой от $$$1$$$ до $$$n$$$), и дети не могут поставить ловушку в точке $$$0$$$, так как они боятся лягушек.

Можете ли вы помочь Славику и Михаю определить, сколько лягушек они могут поймать, используя ловушку?

Входные данные

Первая строка ввода содержит одно целое число $$$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$$$ и мгновенно поймать всех трех лягушек.