给你一个表 $$$a$$$,大小为 $$$n \times m$$$。我们将考虑从上到下编号从 $$$1$$$ 到 $$$n$$$ 的表行,以及从左到右从 $$$1$$$ 到 $$$m$$$ 编号的列。我们将第 $$$i$$$ 行和第 $$$j$$$ 列中的单元格表示为 $$$(i, j)$$$。在单元格 $$$(i, j)$$$ 中写有一个数字 $$$(i - 1) \cdot m + j$$$,即 $$$a_{ij} = (i - 1) \cdot m + j$$$。
一只乌龟最初站在单元格 $$$(1, 1)$$$ 中,它想要来到单元格 $$$(n, m)$$$。从单元格 $$$(i, j)$$$ 可以一步转到单元格 $$$(i + 1, j)$$$ 或 $$$(i, j + 1)$$$(如果存在)之一。路径是一个单元序列,其中序列中每两个相邻的单元都满足以下条件:乌龟可以一步从第一个单元到达第二个单元。路径的成本是写入该路径的单元格中的数字的总和。
例如,当 $$$n = 2$$$ 和 $$$m = 3$$$ 时,表格将如上所示。海龟可以走以下路径:$$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3)$$$。这种方式的成本等于$$$a_{11} + a_{12} + a_{13} + a_{23} = 12$$$。另一方面,路径 $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 1)$$$ 和 $$$(1, 1) \rightarrow (1, 3)$$$ 是不正确的,因为在第一条路径中,海龟无法迈出一步 $$$(2, 2) \rightarrow (2, 1)$$$,而在第二条路径中,它也无法迈出一步。步骤 $$$(1, 1) \rightarrow (1, 3)$$$。
您需要告诉海龟从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的路径的最小可能成本。请注意,单元格 $$$(1, 1)$$$ 和 $$$(n, m)$$$ 是路径的一部分。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 10^4$$$) — 分别是表 $$$a$$$ 的行数和列数。
输出
对于每个测试用例,输出一个整数 - 从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的路径的最小可能成本。
示例
输入 #1
7 1 1 2 3 3 2 7 1 1 10 5 5 10000 10000
输出 #1
1 12 13 28 55 85 500099995000
注意
在第一个测试用例中,唯一可能的路径由单个单元格 $$$(1, 1)$$$ 组成。
语句中显示了第二个测试用例中成本最小的路径。
在第四个和第五个测试用例中,从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 只有一条路径。两条路径都会访问表中的每个单元格。