Let $n$ be a natural number. We have $n$ colors. Each of the numbers $1, 2, 3,... , 1000$ was colored with one of the $n$ colors. It is known that, for any two distinct numbers, if one divides the other then these two numbers have different colors. Determine the smallest possible value of $n$.