Class Pairings

Interview

Time limit1sMemory limit128 MB

Summary

Count the ways to split N students into pairs for each test case and print the result modulo 1000.

Level: Easy3 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1
Input
```
4
2
4
6
12
```
Expected output
```
1
3
15
395
```