Западно-Китайская олимпиада по математике 2005 года | Казахстанские олимпиады

Пусть $S = \{1, 2, 3, \ldots , 2005\}$. Найдите наименьшее $n$ такое, что среди любых $n$ попарно взаимнопростых чисел из $S$ есть хотя бы одно простое.