IT-CESENATICO 2005 Problem 4

Determine all $n \geq 3$ for which there are $n$ positive integers $a_1, \cdots , a_n$ any two of which have a common divisor greater than $1$ , but any three of which are coprime. Assuming that, moreover, the numbers $a_i$ are less than $5000$ , find the greatest possible $n$ .