1089. 一鸣师姐种田

一鸣师姐非常担心自己 35 岁时失业,决定提前学习务农技术啦!

一鸣师姐有一块 m \times n 的矩形田地,一鸣师姐每次都会从矩形田地中划分一块小正方形区域进行种地。小正方形的四条边都必须和矩形的四条边分别平行或重合;选择小正方形区域之前必须确保小正方形区域中没有任何一块地被种过,一旦选择了一个小正方形区域,就必须把整个小正方形区域全部种完,种过的地不能再种。

假设一次种地耗费体力值恰好是所种正方形周长的值。由于一鸣师姐很懒,想花最少的体力值去不遗漏、不重复地种完这块田地,请你帮忙求出最小体力值。

输入

输入包含多组测试用例。

输入的第 1 行包含一个整数 T \ (1 \leq T \leq 10),代表你需要处理 T 组测试用例。

每组用例输入只有 1 行,包含两个用空格间隔的整数 m,n \ (1 \leq m,n \leq 10^4),表示矩形田地的长和宽。

可以证明在给定的条件下,必定存在至少一种方法能将田地不遗漏、不重复地种完。

输出

对于每组测试用例,输出一个整数,表示最小的体力值。

样例

标准输入 复制文本
2
2 3
5 1
标准输出 复制文本
16
20

提示

样例包含 2 组测试用例。

1 组测试用例中,一鸣师姐要种 3 次地,前 2 次各种一块 1 \times 1 的地,第 3 次种一块 2 \times 2 的地,耗费的体力值为 4 \times 2 + 8=16

2 组测试用例中,一鸣师姐要种 5 次地,每次种一块 1 \times 1 的地,耗费的体力值为 4 \times 5=20

来源

2020 软件学院 AK 杯程序设计竞赛

单点时限 1 秒
内存限制 128 MB
提交 1158
通过 220