匹配

给出  行  列的网格，你可以选择任意两个网格配对，每个网格最多只能与一个网格配对，也可以不与任何网格配对。定义关于两个网格  的权值函数 ：

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

从标准输入中读取数据。

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

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

数据范围: 对于所有数据，，，。

其中1/6的数据 max(n,m)<=1000

输出到标准输出中。

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

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

0
1
4
7
 样例解释 

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

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

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


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