2117. Seamild的作业I

单点时限: 2.0 sec

内存限制: 256 MB

Seamild 是计算机系的一名学生,今天有一道 windows 作业。要求她写一个程序,画一条从 (0,0) 点到 (A,B) 点的线段 ,Seamild 把平面分成 1×1 的正方形小格子,如果 (0,0) 到 (A,B) 的这条线段与这些小格子有严格的多余 1 个交点,那么这个小格子就被涂成黑色,反之则为白色,如下图所示 :

现在 Seamild 想知道黑色的格子有多少个?你能帮帮她么?

输入格式

第 1 行有一个正整数 N(1 ≤ N ≤ 60),表示有几组测试数据,接下来 N 行,每行两个正整数 A,B(1≤A,B≤10^14)

输出格式

对于每组输入,输出黑色格子的数目。

样例

Input
2
3 2
4 3
Output
4
6

10 人解决,74 人已尝试。

14 份提交通过,共有 207 份提交。

8.4 EMB 奖励。

创建: 11 年,8 月前.

修改: 2 年,5 月前.

最后提交: 8 月前.

来源: partychen

题目标签