A. Brick Wall-Toy模板网

这篇具有很好参考价值的文章主要介绍了A. Brick Wall。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A brick is a strip of size 1×k1×�, placed horizontally or vertically, where k� can be an arbitrary number that is at least 22 (k≥2�≥2).

A brick wall of size n×m�×� is such a way to place several bricks inside a rectangle n×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×m�×� rectangle belongs to exactly one brick. Here n� is the height of the rectangle n×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 00 horizontal bricks and 22 vertical ones, then the stability will be −2−2, not 22.

What is the maximal possible stability of a wall of size n×m�×�?

It is guaranteed that under restrictions in the statement at least one n×m�×� wall exists.

Input

The first line of the input contains one integer t� (1≤t≤100001≤�≤10000), the number of test cases.

The only line of each test case contains two integers n� and m� (2≤n,m≤1042≤�,�≤104).

Output

For each test case, print one integer, the maximum stability of a wall of size n×m�×�.

Example

input

Copy

2 2

7 8

16 9

3 5

10000 10000

output

Copy

Note

In the 1st test case, the maximum stability of 22 is obtained by placing two horizontal bricks 1×21×2 one on top of the other.

In the 2nd test case, one can get the maximum stability of 2828 by placing 44 horizontal bricks 1×21×2 in each of the 77 rows.

解题说明：此题是一道模拟题，可以采用贪心算法，细分析能得知，为了让数值最大，就是水平砖的数目越多越好，于是k就为2，得到砖数为m/2，然后再放n行即可。文章来源地址https://www.toymoban.com/news/detail-831608.html

#include<stdio.h>
int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		m = m / 2;
		printf("%d\n", n * m);
	}
	return 0;
}

到了这里，关于A. Brick Wall的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！