Хорошее подмножество

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

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

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

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

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

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

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