Friend numbers P22662

Let x₁, …, 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:

• gcd(x_i, x_j) > 1;
• x_i is a friend of some x_k, and x_j is also a friend of x_k.

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.