1333:走方格-3

时间限制: 2 S | 内存限制: 65536 KB
Accept: 1 | Submit: 1
[提交] [状态] [讨论版]
描述

在一张有 n × m 个方格的地图中,每个方格都有一条通向相邻方格的路,如下是一张 2 × 2 的地图:


图中所有的路都以箭头的形式标出,现在你可以从任意一个方格出发,规定每条路最多走一次,请问,你最多可以走多少条路。

输入

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 1000)

每组案例包含两个正整数 n 和 m。(3 <= n + m <= 200000)

输出

针对每组案例,输出你最多可以在 n × m 的地图中走过的路数,然后换行。

样例输入

1

2 2

样例输出

8

HINT

如图所示,我们可以选择从左上角的方格出发,按照“右下左上下右上左”的路线走完所有的路。

来源
19-20(2)第3次线上赛