Friend numbers P22662

Let $x_1, \dots, 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 \ge 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.