Question 39
Let $n$ be a positive integer. Each number from $1, 2, 3, \ldots, 1000$ was painted one of $n$ colors. It turned out that every two distinct numbers, one of which is a divisor of the other one, have different colors. Find the smallest $n$ for which such situation is possible.