CF1700A.Optimal Path

You are given a table $a$ of size $n \times m$. We will consider the table rows numbered from top to bottom from $1$ to $n$, and the columns numbered from left to right from $1$ to $m$. We will denote a cell that is in the $i$-th row and in the $j$-th column as $(i, j)$. In the cell $(i, j)$ there is written a number $(i - 1) \cdot m + j$, that is $a_{ij} = (i - 1) \cdot m + j$.

A turtle initially stands in the cell $(1, 1)$ and it wants to come to the cell $(n, m)$. From the cell $(i, j)$ it can in one step go to one of the cells $(i + 1, j)$ or $(i, j + 1)$, if it exists. A path is a sequence of cells in which for every two adjacent in the sequence cells the following satisfies: the turtle can reach from the first cell to the second cell in one step. A cost of a path is the sum of numbers that are written in the cells of the path.

For example, with $n = 2$ and $m = 3$ the table will look as shown above. The turtle can take the following path: $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3)$. The cost of such way is equal to $a_{11} + a_{12} + a_{13} + a_{23} = 12$. On the other hand, the paths $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 1)$ and $(1, 1) \rightarrow (1, 3)$ are incorrect, because in the first path the turtle can't make a step $(2, 2) \rightarrow (2, 1)$, and in the second path it can't make a step $(1, 1) \rightarrow (1, 3)$.

You are asked to tell the turtle a minimal possible cost of a path from the cell $(1, 1)$ to the cell $(n, m)$. Please note that the cells $(1, 1)$ and $(n, m)$ are a part of the way.

给你一个大小为 $n \times m$ 的表格 $a$。我们将表格的行从上到下编号为 $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)$ 一步移动到 $(2, 1)$；而在第二条路径中，乌龟也无法从 $(1, 1)$ 一步移动到 $(1, 3)$。

你需要告诉乌龟：从单元格 $(1, 1)$ 到单元格 $(n, m)$ 的所有可能路径中，最小可能的代价是多少？请注意，起点 $(1, 1)$ 和终点 $(n, m)$ 均属于路径的一部分。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of test cases follows.

A single line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^4$) — the number of rows and columns of the table $a$ respectively.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例占一行，包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^4$），分别表示表格 $a$ 的行数和列数。

For each test case output a single integer — a minimal possible cost of a path from the cell $(1, 1)$ to the cell $(n, m)$.

对于每个测试用例，输出一个整数——从单元格 $(1, 1)$ 到单元格 $(n, m)$ 的路径的最小可能代价。

In the first test case the only possible path consists of a single cell $(1, 1)$.

The path with the minimal cost in the second test case is shown in the statement.

In the fourth and the fifth test cases there is only one path from $(1, 1)$ to $(n, m)$. Both paths visit every cell in the table.

在第一个测试用例中，唯一可能的路径仅包含单个单元格 $(1, 1)$。

第二个测试用例中代价最小的路径已在题目陈述中给出。

在第四个和第五个测试用例中，从 $(1, 1)$ 到 $(n, m)$ 只存在一条路径。这两条路径均遍历表格中的每个单元格。