Orders and Primitive Roots · Superchallenge problem

Among all integers $a$ with $\gcd(a, 1000) = 1$, what is the largest possible order of $a$ modulo $1000$?