In a $25 \times n$ grid, each square is colored with a color chosen among $8$ different colors. Let $n$ be as minimal as possible such that, independently from the coloration used, it is always possible to select $4$ columns and $4$ rows such that the $16$ squares of the intersections are all of the same color. Find the remainder when $n$ is divided by $1000$.

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