Азиатско-Тихоокеанская математическая олимпиада, 1995 год

$a_1$, $a_2$, $\dots$, $a_n$ — последовательность целых чисел из отрезка $[2, 1995]$ такая, что
(1) любые два члена последовательности взаимно просты;
(2) каждый член последовательности является либо простым числом, либо произведением различных простых чисел.
Найдите наименьшее $n$, такое, что в последовательности $a_i$ наверняка будет по крайней мере одно простое число.