← 返回题目列表

Codeforces · 2063/A

A. 最小互质

中文机器翻译题面 查看原题

今天,小约翰用了所有积蓄购买了一段。他想在这片土地上建造一座房子。

如果 $$$l$$$ 和 $$$r$$$ 互质$$$^{\text{*}}$$$,则正整数 $$$[l,r]$$$ 称为互质。

如果互质段 $$$[l,r]$$$ 不包含 $$$^{\text{†}}$$$ 任何不等于自身的互质段,则称为最小互质段。为了更好地理解这个声明,你可以参考注释。

给定 $$$[l,r]$$$(正整数段),找到 $$$[l,r]$$$ 中包含的最小互质段的数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的唯一行由两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le 10^9$$$) 组成。

输出

对于每个测试用例,在单独的行上输出 $$$[l,r]$$$ 中包含的最小互质段的数量。

示例

输入 #1

6
1 2
1 10
49 49
69 420
1 1
9982 44353

输出 #1

1
9
0
351
1
34371

注意

在第一个测试用例中,给定的段是 $$$[1,2]$$$。 $$$[1,2]$$$ 中包含的段如下。

- $$$[1,1]$$$:该段是互质的,因为数字 $$$1$$$ 和 $$$1$$$ 是互质的,并且该段内部不包含任何其他段。因此,$$$[1,1]$$$ 是最小互质。
- $$$[1,2]$$$:该段是互质的。然而,由于它包含 $$$[1,1]$$$,它也是互质的,因此 $$$[1,2]$$$ 不是最小互质。
- $$$[2,2]$$$:此段不是互质的,因为 $$$2$$$ 和 $$$2$$$ 共享 $$$2$$$ 正公约数:$$$1$$$ 和 $$$2$$$。

因此,段 $$$[1,2]$$$ 包含 $$$1$$$ 最小互质段。