310989: CF1918A. Brick Wall

A. Brick Walltime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

A brick is a strip of size $1 \times k$, placed horizontally or vertically, where $k$ can be an arbitrary number that is at least $2$ ($k \ge 2$).

A brick wall of size $n \times m$ is such a way to place several bricks inside a rectangle $n \times m$, that all bricks lie either horizontally or vertically in the cells, do not cross the border of the rectangle, and that each cell of the $n \times m$ rectangle belongs to exactly one brick. Here $n$ is the height of the rectangle $n \times m$ and $m$ is the width. Note that there can be bricks with different values of k in the same brick wall.

The wall stability is the difference between the number of horizontal bricks and the number of vertical bricks. Note that if you used $0$ horizontal bricks and $2$ vertical ones, then the stability will be $-2$, not $2$.

What is the maximal possible stability of a wall of size $n \times m$?

It is guaranteed that under restrictions in the statement at least one $n \times m$ wall exists.

Input

The first line of the input contains one integer $t$ ($1 \le t \le 10\,000$), the number of test cases.

The only line of each test case contains two integers $n$ and $m$ ($2 \le n,\,m \le 10^4$).

Output

For each test case, print one integer, the maximum stability of a wall of size $n \times m$.

ExampleInput

5
2 2
7 8
16 9
3 5
10000 10000

Output

2
28
64
6
50000000

Note

In the 1st test case, the maximum stability of $2$ is obtained by placing two horizontal bricks $1 \times 2$ one on top of the other.

In the 2nd test case, one can get the maximum stability of $28$ by placing $4$ horizontal bricks $1 \times 2$ in each of the $7$ rows.

题目大意：
题目描述了一种用砖块拼成的墙，每个砖块是大小为 $1 \times k$ 的条状物，可以水平或垂直放置，其中 $k \geq 2$。这些砖块被放置在一个 $n \times m$ 的矩形内，要求所有砖块要么水平放置要么垂直放置，不能超出矩形的边界，且矩形的每个单元格恰好属于一个砖块。墙的稳定性定义为水平砖块数量与垂直砖块数量之差。需要计算给定尺寸 $n \times m$ 的墙的最大可能稳定性。

输入输出数据格式：
- 输入：
- 第一行包含一个整数 $t$（$1 \leq t \leq 10,000$），表示测试用例的数量。
- 每个测试用例包含一行，有两个整数 $n$ 和 $m$（$2 \leq n, m \leq 10^4$）。
- 输出：
- 对于每个测试用例，输出一行，包含一个整数，表示尺寸为 $n \times m$ 的墙的最大稳定性。

示例：
- 输入：
```
5
2 2
7 8
16 9
3 5
10000 10000
```
- 输出：
```
2
28
64
6
50000000
```题目大意： 题目描述了一种用砖块拼成的墙，每个砖块是大小为 $1 \times k$ 的条状物，可以水平或垂直放置，其中 $k \geq 2$。这些砖块被放置在一个 $n \times m$ 的矩形内，要求所有砖块要么水平放置要么垂直放置，不能超出矩形的边界，且矩形的每个单元格恰好属于一个砖块。墙的稳定性定义为水平砖块数量与垂直砖块数量之差。需要计算给定尺寸 $n \times m$ 的墙的最大可能稳定性。 输入输出数据格式： - 输入： - 第一行包含一个整数 $t$（$1 \leq t \leq 10,000$），表示测试用例的数量。 - 每个测试用例包含一行，有两个整数 $n$ 和 $m$（$2 \leq n, m \leq 10^4$）。 - 输出： - 对于每个测试用例，输出一行，包含一个整数，表示尺寸为 $n \times m$ 的墙的最大稳定性。 示例： - 输入： ``` 5 2 2 7 8 16 9 3 5 10000 10000 ``` - 输出： ``` 2 28 64 6 50000000 ```