시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB364703919.697%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

4
6 15 10 42

예제 출력 1

3

예제 입력 2

3
2 2 2

예제 출력 2

3

예제 입력 3

1
35

예제 출력 3

1

노트

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