406996: GYM102672 D Good Subset

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Good Subsettime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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!

Input

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

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

ExamplesInput
4
6 15 10 42
Output
3
Input
3
2 2 2
Output
3
Input
1
35
Output
1
Note

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

加入题单

上一题 下一题 算法标签: