C. 影子戏
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
时至今日,我依然逃避。

过了这么多年,我本以为自己改变了、变强了、从羊变成了狼,不用再畏惧任何事。

然而,我还是无法摆脱那一年的噩梦。

白袍——乌甲素包巾!丈八蛇矛——手内握哎 。

影子戏里,是刘关张三人大战赤兔吕布的场景。

白幕可以抽象成一个 $$$n\times m$$$ 的网格,满穗希望在上面放若干个骑兵。

满穗希望它们互不攻击。

请你帮忙计算网格中最多能放多少个互不攻击的骑兵。

形式化的:给定一张 $$$n\times m$$$ 的网格。

计算这张网格内最多能放多少个互不攻击的骑兵。

对于位于 $$$(i, j)$$$ 的骑兵,可以攻击到的位置为 $$$(i-2, j+1)$$$,$$$(i-1, j+2)$$$,$$$(i+1, j+2)$$$,$$$(i+2, j+1)$$$,$$$(i+2, j-1)$$$,$$$(i+1, j-2)$$$,$$$(i-1, j-2)$$$,$$$(i-2, j-1)$$$,输入下图所示:

Input

有多组测试数据。第一行输入一个正整数 $$$T$$$($$$1\le T \le 10^5$$$),表示测试数据组数。

每组测试数据输入一行,其中有两个正整数 $$$n$$$,$$$m$$$($$$1\le n, m\le 10^9$$$),表示网格大小。

Output

每组测试数据输出一行,包含一个整数,表示答案。

Example
Input
2
2 4
5 4
Output
4
10