Find the smallest natural number $n$ such that for any coloration of the numbers $1, 2, \dots, n$ with three different colors, there exist two numbers of the same color, whose difference is a perfect square.

Let's think step by step and output the final answer within \boxed{}.
user