P5456 [THUPC 2018] Cake

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.

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$)

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$.

### 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](http://pony.ai) for supporting this contest. Resources such as solutions can be found at . Translated by ChatGPT 5