Park Lighting

题意翻译

给你 $n\cdot m$ 的网格。  你可以在两个网格之间的边上放一个灯，这个灯将会照亮这两个网格。(可以按照图理解一下，黄色的圆点即为灯) 求出照亮所有的 $n\cdot m$ 个格子的最小需要的灯数。 一共 T 组数据。

题目描述

由于本场题面违反互联网相关法律，不予展示原题面。

输入输出格式

输入格式

输出格式

输入输出样例

输入样例 #1

5
1 1
1 3
2 2
3 3
5 3

输出样例 #1

1
2
2
5
8

说明

Possible optimal arrangement of the lanterns for the $ 2 $ -nd test case of input data example:  Possible optimal arrangement of the lanterns for the $ 3 $ -rd test case of input data example: