The Twin Tower

In recent years so many twins have enrolled at Leiden University that housing them has become a big problem. To accommodate everyone, the university plans to build a skyscraper of $N$ floors, with 9 rooms on each floor laid out in a $3 \times 3$ square. Everyone must be able to get a room next to, directly above, or directly below their twin. More precisely, the two rooms of a twin must either lie on opposite sides of a common wall, or the floor of one room must be the ceiling of the other. For privacy, students never share a room.

Count all ways to pair up the rooms so that no room is left unpaired, modulo $10007$.

The first line contains a single integer $T$: the number of test cases. Each test case is a single line containing one integer $N$ with $0 \le N \le 5000$.

For each test case, output on its own line the number of valid pairings, taken modulo $10007$.