406807: GYM102562 H Long Path

Peter is captive in W's maze which can be represented as a tridimensional matrix with lengths $$$N$$$, $$$M$$$ and $$$K$$$. Initially, Peter is in cell (1,1,1) and he needs to get to cell ($$$N$$$,$$$M$$$,$$$K$$$) to escape. From a cell, he can move to any other cell that has a wall in common with your cell (maximum $$$6$$$ other cells). Now, everyone expects Peter to escape in the minimum number of steps, but he can do better than that. He thinks of getting out with the maximum number of steps, such that he doesn't visit a cell more than once in his path. Help Peter find the length of this path!

The first line of the input contains a number $$$1 \leq T \leq 200.000$$$, the number of tests. The next $$$T$$$ lines each contain the description of a test, 3 positive integers $$$1 \leq N, M, K \leq 10^6$$$.

The output should contain $$$T$$$ lines, each containing an answer to a test.

3
1 2 2
10 10 10
190700 80700 150700

3
1000
2319196143000000