Given a grid with rows and columns, in this grid, you can choose two different grid points and match them into a pair. Notice that a point can only be matched with no more than one point. It means unmatched points are allowed. We define a weight function for a pair of points as the following form:
The weight of a possible matching scheme is defined as the sum of weights that the matching pairs given. Your task is to calculate the maximum possible weight of all matching schemes.
接下来 行，每行三个整数 ，表示网格的行数、列数以及权值函数中的常数 。
Read from the standard input.
The first line contains a single integer which means the number of the test cases.
Each of the following lines contains three integers which means the height and the width of the grid, and the constant in the weight function.
Write to the standard output.
For each test case, output a line containing a single integer — the maximum of the weight of possible matching plans.
As for grid, there is no point for the only one to match, so the answer is .
As for grid, we match the only two points into a pair, so the answer is .
As for grid, we match the top left point and the bottom right one into a pair, the top right point and the bottom left one into a pair. The answer is , as shown by the following picture.
As for grid, we match the top left point and the bottom middle one, the top middle point and the bottom right one, the top right point and the bottom left one. The answer is , as shown by the following picture.