H. Hide the Money
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

As Iceberg Corporation kept growing and making significant profit, Yessine went from millionaire to billionaire. He got really greedy and decided to hide his money from the government to avoid taxes. To do so, he decided to put all his money in bags and bury them in Sfax. As you may know from previous Winter Cups, Sfax is an $$$N \times M$$$ rectangular grid. Yessine has $$$K$$$ bags of money. He will hide at most one bag per grid cell. However, he won't place them in random cells. Instead, he will bury a bag in a cell if it maximizes the sum of Manhattan distances from all the other cells in Sfax.

Formally, he wants to maximize $$$S$$$ defined as:

$$$$$$S=\sum\limits_{i=1}^N \sum\limits_{j=1}^M \sum\limits_{k=1}^K D(i,j,k)$$$$$$

where $$$D(i,j,k)$$$ denotes the Manhattan distance between cell ($$$i$$$,$$$j$$$) and the $$$k^{th}$$$ piece.

The Manhattan distance between $$$(x,y)$$$ and $$$(x',y')$$$ is $$$\lvert x'-x \rvert + \lvert y'-y \rvert$$$.

Help Yessine hide the money before the government captures him.

Input

The first line contains an integer $$$1 \le T \le 100$$$ denoting the number of testcases.

Each testcase contains three integers $$$N$$$, $$$M$$$, $$$K$$$ such that $$$1 \le N,M,K \le 2\times 10^{4}$$$ and $$$K \le N \times M$$$.

Output

Print a single integer $$$S$$$: the maximum possible sum.

Example
Input
4
2 2 1
2 2 2
3 3 6
4 4 12
Output
4
8
102
512
Note

It is guaranteed that within the given constraints, for each test case, the result will not exceed $$$10^{18}.$$$