往届 ACM 队训练题 (参考)

1087. 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
不限期开放

题目列表