P9355 "SiR-1" Checkmate

There was originally a very long background story here, but the problem setter thought it was too long, so it was deleted. "Come on, the game has begun."

There is a chessboard with $n$ rows and $m$ columns. You need to place one piece on every cell of this board **one by one in sequence**. Each time you place a piece, you will get some points. The points you get equal the number of adjacent cells (that have no piece placed) among the cells next to the piece **at the moment you place it**. Here, "adjacent" means the four neighboring cells: up, down, left, and right. You want to know, **if you choose the placement order using the best strategy**, what is the maximum possible total score in the end.

**This problem contains multiple test cases.** The first line of input contains a positive integer $T$, which denotes the number of test cases. For each test case, there are two positive integers $n, m$ separated by spaces.

For each test case, output one line representing the maximum score.

**This problem uses bundled tests.** - Subtask 1 (20 points): $n, m \leq 3$, $T \leq 5$. - Subtask 2 (20 points): $n, m \leq 4$, $T \leq 10$. - Subtask 3 (20 points): $n = 1$. - Subtask 4 (20 points): $n = m$. - Subtask 5 (20 points): No special constraints. For all testdata, $1 \leq n, m \leq 10^8$, $1 \leq T \leq 10^5$. Translated by ChatGPT 5