«Клубу неудачников» после победы над Пеннивайзом почти удалось сбежать из заброшенного дома, осталось только решить кодовый замок на двери.
На кодовом замке написано $$$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$$$.