Proof Writing & Problem Solving · Superchallenge problem

With $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$, pigeonhole on the pairs $(F_n \bmod 1000,\ F_{n+1} \bmod 1000)$ proves that some Fibonacci number $F_n$ with $n \ge 1$ is divisible by 1000, without finding it. What is the SMALLEST such $n$?