Description

Recently, Feifei learned how to make cakes. She made a 4D cake for Niuniu. The size of the cake is: $a \times b \times c \times d$.

All surfaces of the cake are covered with cream. Niuniu wants to cut the cake into $1 \times 1 \times 1 \times 1$ small pieces along hyperplanes parallel to the surfaces.

Now, Niuniu wants to know, among these small pieces, how many pieces have $0$ surface, $1$ surface, $2$ surfaces, $\ldots$, $8$ surfaces covered with cream, respectively.

Input Format

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases. ($T \le 10000$)

Each test case is described as follows:

• One line with $4$ positive integers $a$, $b$, $c$, $d$. (All four positive integers are within $10^6$)

Output Format

For each test case, output one line:

• Output $9$ integers, representing the number of small pieces that have $0$ surface, $1$ surface, $2$ surfaces, $\ldots$, $8$ surfaces covered with cream, respectively. Separate the values with a single space. To prevent the answer from being too large, you only need to output each value modulo $2148473648$.

5
2 2 2 3
7 7 8 8
9 9 9 9
3 3 5 6
9 7 5 2

0 0 0 8 16 0 0 0 0
900 1320 724 176 16 0 0 0 0
2401 2744 1176 224 16 0 0 0 0
12 62 108 72 16 0 0 0 0
0 210 284 120 16 0 0 0 0

Hint

Sample Explanation

For the first test case, after cutting a $2 \times 2 \times 2 \times 3$ cake into small pieces, a total of $24$ small cubes are formed. Among them, $16$ pieces are each adjacent to the other $4$ pieces, so they have $4$ faces covered with cream. The other $8$ pieces are each adjacent to the other $5$ pieces, so they have $3$ faces covered with cream.

Copyright Information

From the 2018 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5