jmc

The thousands digit is $\in \{4,5,6\}$. Case $1$: Thousands digit is even $4,6$, two possibilities, then there are only $\frac{10}{2}-1=4$ possibilities for the units digit. This leaves $8$ possible digits for the hundreds and $7$ for the tens places, yielding a total of $2\cdot 8\cdot 7\cdot 4=448$. Case $2$: Thousands digit is odd $5$, one possibility, then there are $5$ choices for the units digit, with $8$ digits for the hundreds and $7$ for the tens place. This gives $1\cdot 8\cdot 7\cdot 5=280$ possibilities. Together, the solution is $448+280=\boxed{728}$.