2858. 危险,距离不能为二

单点时限: 2.0 sec

内存限制: 256 MB

在一个 H*W 的棋盘上,每个格子最多只能放一个棋子。并且如果两个棋子的欧几里得距离为 2 时,这两个棋子能够相互攻击。问棋盘上最多能放几个棋子,能使任意两个棋子互不攻击。

输入格式

第一行有一个正整数 N,表示有多少组测试数据

接下来有 N 行,每一行代表一组数据。每一行有两个数,H,W 表示棋盘的高,宽。

N<200,1<= H,W <= 1000,且都为正整数

欧几里得距离定义为

输出格式

对于每组数据,输出一个值,表示最多能放的棋子的数量、每组数据占一行,不要有多余空格。

样例

Input
3
3 2
3 3
8 5
Output
4
5
20

49 人解决,65 人已尝试。

59 份提交通过,共有 184 份提交。

7.6 EMB 奖励。

创建: 9 年前.

修改: 2 年,5 月前.

最后提交: 6 月,1 周前.

来源: N/A

题目标签