题目描述

给出 $n$ 行 $m$ 列的网格，你可以选择任意两个网格配对，每个网格最多只能与一个网格配对，也可以不与任何网格配对。定义关于两个网格 $A, B$ 的权值函数 $f(A, B)$： $$\begin{aligned} dx &= \left|x_A - x_B\right| \ dy &= \left|y_A - y_B\right| \ f(A, B) &= \begin{cases} dx + dy & , dx + dy \geq k \ 0 & , dx + dy < k \end{cases} \end{aligned}$$

一个配对方案的权值为其所有网格配对的权值之和 $\sum f$。求给出网格中，所有配对方案中权值的最大值。

输入格式

从标准输入中读取数据。

第一行，一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行三个整数 $n, m, k$，表示网格的行数、列数以及权值函数中的常数 $k$。

输出格式

输出到标准输出中。

输出共 $T$ 行，对于每一组数据，输出一行一个整数，表示所有配对方案的配对权值和的最大值。

样例 1

input

4
1 1 0
1 2 0
2 2 1
2 3 1

output

0
1
4
7

对于 $1 \times 1$ 的网格，不存在匹配方案，答案为 $0$。

对于 $1 \times 2$ 的网格，匹配方案唯一，答案为 $1$。

对于 $2 \times 2$ 的网格，左上格与右下格匹配，右上格与左下格匹配，答案为 $4$。如下图所示。

对于 $2 \times 3$ 的网格，左上格与中下格匹配，中上格与右下格匹配，右上格与左下格匹配，答案为 $7$。如下图所示。

样例 2

input

6
23 66 12
233 666 123
2333 6666 1234
23333 6666 1234
2333 66666 1234
23333 66666 12345

output

33759
34876089
34987610889
1166494448889
2682884270889
34998761108889

样例 3

input

4
1 1 0
1 2 0
2 2 1
2 3 1

output

0
1
4
7

样例 4

input

6
23 66 12
233 666 123
2333 6666 1234
23333 6666 1234
2333 66666 1234
23333 66666 12345

output

33759
34876089
34987610889
1166494448889
2682884270889
34998761108889

数据范围与提示

对于所有数据，$1 \leq T \leq 10^5$，$1 \leq n,m \leq 10^6$，$0 \leq k \leq \min(n, m) - 1$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：