Extremal colors integers

Bob colors the first $n$ positive integers using exactly $3$ colors, where each number is colored with exactly one color. Find the smallest value of $n$ such that, for every such coloring, there always exist two numbers of the same color whose positive difference is a perfect square.