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

stdin

6
3 3
3 4
126 74
169 208
1000000000 987654320
976875237 848936273

stdout

6
8
6216
23435
658436213333333334
552869881923181134