并没有人愿意陪可怜的小S玩，所以他只能一个人在棋盘上摆马玩。

现在他想要知道一个$n\times m$的棋盘最多能摆多少个马，使得这些马互不攻击。在$(x,y)$的马可以攻击到$(x\pm 2,y\pm 1)$或$(x\pm 1,y\pm 2)$。

输入格式

第一行一个整数$T$，表示数据组数。

接下来$T$行，每行两个整数$n,m$。

输出格式

对于每组数据，输出一个数表示答案。

样例

样例一

input

2
1 5
2 3

output

5
4

约定与限制

对于$20\%$ 的数据，满足 $n\times m\le 15$。

对于$100\%$ 的数据，满足 $1\le T\le 1000,1\le n,m \le 10^9$。

数据均为随机生成。

时间限制:1s

空间限制:512MB