B. Большой день для Баша
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Баш отправился в путешествие, чтобы стать величайшим мастером Покемонов. Чтобы получить первого покемона, он отправился в лабораторию профессора Зулу. Поскольку Баш — любимый студент профессора, Зулу разрешил ему взять столько покемонов из лаборатории, сколько Баш захочет.

Однако, профессор предупрел Баша, что группа из k > 1 покемонов с силами {s1, s2, s3, ..., sk} склонна к драке между собой, если gcd(s1, s2, s3, ..., sk) = 1 (смотрите примечания для определения gcd).

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

Обратите внимание: Один покемон не может драться сам с собой.

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

Входные данные находятся в двух строках.

Первая строка содержит целое число n (1 ≤ n ≤ 105) — число покемонов в лаборатории профессора.

Следующая строка содержит n целых чисел, где i-е из них равно si (1 ≤ si ≤ 105) — силе i-го покемона.

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

Выведите одно число — максимальное число покемонов, которых Баш может взять.

Примеры
Входные данные
3
2 3 4
Выходные данные
2
Входные данные
5
2 3 4 6 7
Выходные данные
3
Примечание

gcd (наибольший общий делитель) множества натуральных чисел {a1, a2, ..., an} равняется наибольшему натуральному числу, на которое делятся все числа {a1, a2, ..., an}.

В первом примере Баш может взять покемонов с силами {2, 4}, потому что gcd(2, 4) = 2.

Во втором примере Баш может взять покемонов с силами {2, 4, 6}, и не существует группы больше с gcd ≠ 1.