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

시간 제한2초메모리 제한1024 MB

요약

1e18 이하의 수 n개가 주어질 때, 최대공약수가 1보다 큰 가장 큰 부분집합의 크기를 구한다.

난이도: 보통10점 중 6점
유형: 정수론, 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

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

На кодовом замке написано $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$ .

예제3

예제 1
입력
```
4
6 15 10 42
```
예상 출력
```
3
```
예제 2
입력
```
3
2 2 2
```
예상 출력
```
3
```
예제 3
입력
```
1
35
```
예상 출력
```
1
```