406996: GYM102672 D Good Subset

After the victory over Pennywise "The Losers Club" almost succeeded in escaping from the abandoned house, the only thing that is left is to decode the lock on the door.

There are $$$n$$$ integer positive numbers on the lock $$$a_1, a_2, \ldots, a_n$$$. To open it we need to find the size of the biggest subset of these numbers such that the gcd of the elements from the subset is greater than one. The gcd of the subset is the biggest positive integer number such that it divides every element from the subset.

Please, help!

The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of elements.

The second line contains $$$n$$$ positive integers $$$a_i$$$ ($$$2 \leq a_i \leq 10^{18}$$$).

Output one integer — the size of the biggest subset such that the gcd is greater than 1.

4
6 15 10 42

3

3
2 2 2

3

1
35

1

In the first test case one possible answer is $$$\{6, 15, 42\}$$$, the gcd equals $$$3$$$.