L. Two Shortest Paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yessine and Rami are living in Sfax.

Sfax is a rectangular grid of size $$$n\times m$$$. Each cell has a cost. The cost of the cell $$$(i,j)$$$ is $$$a_{i,j}$$$.

Initially, All the costs are unset.

Yessine is living in cell $$$(1,1)$$$ and wants to go to the cell $$$(n,m)$$$, and Rami is living in cell $$$(1,m)$$$ and wants to go to the cell $$$(n,1)$$$.

Rami and Yessine can move to any other cell that share the same edge with their current cell, in other words they can move $$$\textbf{UP}$$$, $$$\textbf{DOWN}$$$, $$$\textbf{LEFT}$$$, or $$$\textbf{RIGHT}$$$.

Between all the paths, to reach their destinations, Yessine will take a path that has a minimum cost. Also, Rami will take independently of Yessine a path that has a minimum cost.

The cost of a path is the sum of all numbers in all cells in this path including the start cell and the end cell.

As Oussama is their best friend, he wanted to put on each cell $$$(i,j)$$$ $$$\textbf{distinct}$$$ strictly positive integers so that the sum of the two costs of paths of Yessine and Rami is as minimal as possible.

Oussama is stuck. Please help him determine what is the minimal sum of the two costs.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10000)$$$ — the number of test cases.

Each test case contains a line of two integers $$$n$$$ and $$$m$$$ denoting the size of the grid $$$(2 \le n,m \le 10^4)$$$

Output

For each test case, print a single integer $$$C$$$ — The minimal sum of the two costs.

Example
Input
3
3 3
5 4
7 3
Output
34
81
94
Note
For the first test case, the following grid describes a possible trajectory taken by Rami and Yessine with a minimal sum of $$$34$$$.