A machine has n gears, each labeled with its tooth count (an integer at least 2). Two gears mesh directly if their tooth counts share a common factor greater than 1. Meshing is transitive: gears connected through a chain of meshing gears form one meshed group.
Report the number of gears in the largest meshed group.
Input format
- Line 1: an integer
n, the number of gears. - Line 2:
nspace-separated integers, the tooth counts. Values may repeat.
Output format
A single integer: the size of the largest meshed group.
Constraints
- 1 <= n <= 30000
- 2 <= tooth count <= 100000