Let x_{1}, …, x_{n} be a non-empty sequence of natural numbers, all of them strictly larger than 1, and let gcd(x, y) stand as usual for the greatest common divisor of x and y. We say that x_{i} is a friend of x_{j} if and only if at least one of these conditions hold:
Write a program such that, given a sequence of numbers, computes the size of the largest set of friends in it.
Input
Input consists of several cases. Every case begins with a number n ≥ 1, followed by n different integer numbers, all them between 2 and 100000.
Output
For every case, print the size of the largest set of friends.
Input
4 21 2 25 14 3 5 18 7
Output
3 1