Хорошее подмножество
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

«Клубу неудачников» после победы над Пеннивайзом почти удалось сбежать из заброшенного дома, осталось только решить кодовый замок на двери.

На кодовом замке написано $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. И чтобы открыть его, нужно найти размер наибольшего подмножества этих чисел, что НОД чисел в подмножестве строго больше единицы. НОД множества чисел — это наибольшее натуральное число, делящее все числа из множества.

Помогите героям справиться с этой задачей!

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

В первой строке дано одно целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — количество натуральных чисел.

Во второй строке даны $$$n$$$ натуральных чисел $$$a_i$$$ ($$$2 \leq a_i \leq 10^{18}$$$).

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

Выведите одно целое число — размер наибольшего подмножества данных чисел, что НОД чисел в этом подмножестве строго больше единицы.

Примеры

Входные данные
4
6 15 10 42
Выходные данные
3
Входные данные
3
2 2 2
Выходные данные
3
Входные данные
1
35
Выходные данные
1

Примечание

В первом тесте можно выбрать множество $$$\{6, 15, 42\}$$$, НОД чисел в этом множестве равен $$$3$$$.