H. The Binary Matrix of All Time
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A binary matrix with $$$n$$$ rows and $$$m$$$ columns is considered good if it has no $$$1 \times 3$$$ or $$$3 \times 1$$$ submatrices consisting of equal elements.

For example, $$$\begin{bmatrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}$$$ and $$$\begin{bmatrix}0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}$$$ are good, while $$$\begin{bmatrix}1 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix} and \begin{bmatrix}1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 1 & 0 \end{bmatrix}$$$ are not.

Given two integers $$$n$$$ and $$$m$$$, what is the maximum number of $$$1$$$'s in a good matrix with $$$n$$$ rows and $$$m$$$ columns?

Input

Each test contains multiple testcases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n,m \le 10^9$$$) — the height and width of the matrix.

Output

For each testcase, print one integer, the maximum number of $$$1$$$'s in a good matrix with $$$n$$$ rows and $$$m$$$ columns.

Example
Input
6
3 3
3 4
126 74
169 208
1000000000 987654320
976875237 848936273
Output
6
8
6216
23435
658436213333333334
552869881923181134