seuOJ530 - 棋盘

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：Div.1, 2025

题目描述

小J面前有一个 $n\times m$ 的棋盘，他手里面还有很多个形如"L"型的拼图，拼图如下图所示：

该拼图可以旋转或反转放入棋盘中

他想问你这个棋盘在拼图不互相重叠的情况下最多能摆多少块拼图。

输入格式

第一行，一个整数 $t(1\le t \le 100)$，代表数据组数。

对于每组数据，输入一行两个整数 $n,m(1\le n,m \le 10^6)$，分别代表棋盘的长和宽。

输出格式

对于每组数据，输出一行一个正整数，代表在拼图不互相重叠的情况下棋盘中最多能摆多少块拼图。

样例

输入样例

4
2 3
3 3
1 100
7 5

输出样例

2
2
0
11

样例解释
样例中第二组和第三组数据分别按照如下方式摆放。