Description

可莉在蒙德城游玩的时候，因为没有路灯，没看到脚下的东西所以被绊倒了，按道理来说在风之城这种事情是不会发生的。

但可莉实在是笨的可爱，这可愁坏了蒙德城的西风骑士团，所以下令让你去安装路灯。为了不让可莉再次受到伤害，他让你点亮所有的地方。

为了简化问题，我们将蒙德城想象成一个的单元格，单元格之间的边界就是街道。你只能将路灯当到街道上，然后照亮相邻的两个单元格（如右上角的路灯），如果你放置到了边界上的街道，那么他只能照亮一个单元格（如左上角的路灯）

由于蒙德城经费不足，西风骑士团想要你用最少的路灯点亮所有的单元格。

Input Format

第一行包含一个整数，表示测试数据的组数。

接下来行，每一行两个整数，表示蒙德城的大小。

Output Format

对于每一组测试数据，你需要输出一个整数，表示点亮所有单元格所需最少路灯的数量。

4
1 3
2 2
3 3
5 3​

2
2
5
8​

Hint

对于的蒙德城，只需要安置两个路灯

对于的蒙德城，也只需要安装两个路灯。