Cube

We have a number of monochrome unit cubes colored with n different colors (we have more of each color). Our target is to build with 8 randomly picked cubes as many differently colored 2 × 2 × 2 cubes as possible. Two cubes are considered identical if we can get it through rotating another construction, otherwise they are considered different colorings.

Example: having two colors, i.e., black and white unit cubes, we can build 23 differently colored 2 × 2 × 2 cubes.

Considering that there are enough cubes in n different colors, compute the number of differently colored 2 × 2 × 2 cubes that can be built using them.

Input Specification

On the first line of the input, we have the number C of test cases. Each of the next C lines contains a number n, the number of the different colors of the unit cubes (0 ≤ n ≤ 2 000 000 000).

Output Specification

The output will contain C lines, every line will contain the number of differently colored cubes modulo 666013 that can be obtained with n colors. The order of the numbers will correspond to the input lines' order.

Sample Input 1

1. 1
2. 2

download as text file

Output for Sample Input 1

1. 23

download as text file

Explanation of Sample Input 1

We have a single case, use two colors, e.g., black and white. Cases:

• 1 case using 8 white unit cubes;
• 1 case using 7 white unit cubes and 1 black unit cube;
• 3 cases using 6 white unit cubes and 2 black unit cubes;
• 3 cases using 5 white unit cubes and 3 black unit cubes;
• 7 cases using 4 white unit cubes and 4 black unit cubes;
• 3 cases using 3 white unit cubes and 5 black unit cubes;
• 3 cases using 2 white unit cubes and 6 black unit cubes;
• 1 case using 1 white unit cube and 7 black unit cubes;
• 1 case using 8 black unit cubes;

Total: 23 different colorings.

Sample Input 2

1. 4
2. 2
3. 1000
4. 5000
5. 2000000000

download as text file

Output for Sample Input 2

1. 23
2. 45538
3. 280943
4. 185532

download as text file

Explanation of Sample Input 2

We have four cases with 2, 1000, 5000, and 2 000 000 000 colors. Results modulo 666013 are: 23, 45538, 280943, and 185532.