VN-TST 2004 Problem 1

Let us consider a set $S = \{ a_1 < a_2 < \ldots < a_{2004}\}$ , satisfying the following properties: $f(a_i) < 2003$ and $f(a_i) = f(a_j) \forall i, j$ from $\{1, 2,\ldots , 2004\}$ , where $f(a_i)$ denotes number of elements which are relatively prime with $a_i$ . Find the least positive integer $k$ for which in every $k$ -subset of $S$ , having the above mentioned properties there are two distinct elements with greatest common divisor greater than 1.