Михай и Славик смотрели на группу из \(n\) лягушек, пронумерованных от \(1\) до \(n\), которые изначально находились в точке \(0\). Лягушка \(i\) может прыгнуть на расстояние \(a_i\).
Каждую секунду лягушка \(i\) прыгает на \(a_i\) единиц вперед. Прежде чем лягушки начнут прыгать, Славик и Михай могут поставить ровно одну ловушку в координате, чтобы поймать всех лягушек, которые когда-либо пройдут через эту координату.
Однако, дети не могут уйти далеко от своего дома, поэтому они могут поставить ловушку только в одной из первых \(n\) точках (то есть в точке с координатой от \(1\) до \(n\)), и дети не могут поставить ловушку в точке \(0\), так как они боятся лягушек.
Можете ли вы помочь Славику и Михаю определить, сколько лягушек они могут поймать, используя ловушку?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество лягушек, которых Славик и Михай могут поймать с помощью ловушки.
Примечание
В первом примере лягушки будут прыгать следующим образом:
- Лягушка 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\) и мгновенно поймать всех трех лягушек.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
3
3
5
0
4
4
|