Class Pairings

There are N students in Hector's class, and N is even. Hector wonders who will sit next to whom at the same desk in the coming school year.

In how many different ways can all of the students be split into pairs?

Two ways are considered different if at least one student is paired with a different partner in one way than in the other.

The first line contains the number of test cases Z ($1 \le Z \le 10$). Then Z test cases follow.

Each test case consists of a single line containing an even natural number N ($2 \le N \le 10^6$, N is even), the number of students in the class.

For each test case, compute the number of different ways to pair up the students. Since this number can be very large, print its remainder modulo $1000$. Print each result on its own line.