题目描述

给出 $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$ 行，对于每一组数据，输出一行一个整数，表示所有配对方案的配对权值和的最大值。

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

0
1
4
7

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

33759
34876089
34987610889
1166494448889
2682884270889
34998761108889

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

0
1
4
7

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

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

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

子任务编号	分值(百分比)	$T$	$n, m$	特殊限制
$1$	$10$	$\leq 20$	$\leq 2000$	$n \leq 2$
$2$	$15$	$\leq 5$	$\leq 8$	$n \times m \leq 10$ 且 $k = \min(n, m) - 1$
$3$	$25$	$\leq 3$	$\leq 16$	无
$4$	$18$	$\leq 100$	$\leq 5000$	$n = m$ 且 $n \equiv 0 \pmod 2$
$5$	$32$	$\leq 10^5$	$\leq 10^6$	无