Background

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."

Problem Description

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.

Input Format

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.

Output Format

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

4
1 3
2 2
3 4
7 13

2
4
17
162

Hint

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