HZNUOJ

神枪手JoneySun (a little bit hard Version)

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:54     AC:16     Score:100.00

Description

Easy Version 和 a little bit hard Version 只有数据范围的区别

JoneySun被邪恶的wifepie困在了一个由$1\times1$的网格分割的监狱里,邪恶的wifepie为了看JoneySun的笑话,在监狱里的某处监视着JoneySun,幸运的是JoneySun手中有一把枪,不幸的是wifepie掌握了分身术。

我们认为这个监狱是一个$2n\times 2m$的网格,JoneySun被困在最中间,除了JoneySun所在处,网格其余的交点上都有一个wifepie的分身。JoneySun的枪射程是无限远,如果子弹射中分身,那么分身会消失,子弹继续沿直线行进。如果子弹射中wifepie本体,wifepie就会被JoneySun消灭。JoneySun想知道消灭wifepie最多需要多少子弹。

Input

第一行一个整数$T(1\le T \le 100)$表示共有$T$组输入

第二行两个整数$n,m(1\le n,m\le 5\times 10^6)$,含义见题面

Output

每组输入输出一个整数表示最多需要的子弹数量

Samples

input
1 1 1
output
8

Hint

如图所示,红点表示JoneySun所在位置,蓝点表示wifepie的分身,JoneySun最多需要8颗子弹就可以消灭wifipie所有的分身

Author

BAO, Min