今天,小约翰用了所有积蓄购买了一段。他想在这片土地上建造一座房子。
如果 $$$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$$$ 最小互质段。