Now that we've taken a look at how knights move around on a flat chessboard, let's abstract this to a 3D chessboard.
The board will instead be a lattice of cells, such that the knight piece may occupy any cell with coordinates (x, y, z).
Recall that by standard chess rules, a knight's move consists of sliding 1 unit along one axis, and sliding 2 units along the other axis.
The knight will follow the same rules for navigting through the 3D lattice, except that he now may choose 2 of the available 3 axes for any turn.
For example, the knight begins at the cell (0, 0, 0), but in a single turn he may move 1 unit along the z axis and -2 units along the x axis to end up in the cell at (-2, 0, 1). From any given cell, there are 24 possible destination cells. This means that after turn 1, there are 25 cells able to be visited (the starting cell counts towards this total). After turn 2, there are 225 cells able to visited.
Given an integer, determine the number of cells able to be visited by the knight after that many moves.
Input Data
The first line will be Q, the quantity of testcases.
Q space-separated values will follow, each a single integer n.
Answer
Should consist of Q space-separated integers, corresponding to the number of cells able to be visited by the knight after n turns in each testcase.
Answers may be very large, so report each answer modulo 9001.
Example
input data:
3
1
2
123
answer:
25 225 7522