J. Stop, Grid Please No More
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You finished the last puzzle, and got sent to another world again. This time there is no Vanilla here, only pwp cosplaying Vanilla, sitting on the only table in the blank world.

Who are you, and why are you wearing Pin... ahem, Vanilla's clothes? Before the question in your heart could even be spoken, pwp answered, "pwp is pwp, meow. Strange, this is clearly your dream, so why would you dream of pwp, meow?" pwp said, swinging her legs. A dream? Then... "Yes. But don't think about doing anything weird in a dream, meow; your thoughts are showing." pwp said, and rang the bell on the table a few times. Ugh...

"Shouldn't getting out of the dream be more important, meow?" pwp pointed at the ground. A grid again? "Since you came down from the last layer of the dream, you should be able to solve this puzzle, meow." After saying that, pwp swept a +4 card off the table with her tail. It landed on the edge of a cell, and that edge suddenly became more visible and wider.

Human, the words above do not matter meow——pwp is here $$$\sim$$$

Given an $$$n \times m$$$ grid, place in each cell a square with one marked side:

Use $$$1, 2, 3, 4$$$ to represent the four possible directions of the marked side. Find the maximum area of a closed region that can be enclosed in this grid.

Input

Each test file contains multiple test cases. The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 1500)$$$, the number of test cases.

For each test case, input one line with two integers $$$n, m$$$ $$$(1 \leq n, m \leq 10^6, 1 \leq n \times m \leq 10^6)$$$, representing the size of the grid.

It is guaranteed that the sum of $$$n \times m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one integer on the first line, representing the maximum area of an enclosed region that can be formed; if it is impossible to form an enclosed region with an area greater than $$$0$$$, output $$$0$$$.

Example
Input
2
2 5
4 4
Output
6
8
Note

The figure below explains the sample.

It is easy to prove that there is no strictly better answer.

The following part is to avoid ambiguity. For the construction shown below,

there are two enclosed regions at the same time, with areas $$$12$$$ (the light blue part) and $$$3$$$ (the yellow part).