← 返回题目列表

Codeforces · 1780/E

E. 仗助和完整图

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

Josuke 收到了一个巨大的无向加权完整 $$$^\dagger$$$ 图 $$$G$$$ 作为他祖父的礼物。该图包含 $$$10^{18}$$$ 个顶点。该礼物的特殊之处在于不同顶点 $$$u$$$ 和 $$$v$$$ 之间的边的权重等于 $$$\gcd(u, v)^\ddagger$$$。仗助决定尝试并制作一个新图表$$$G'$$$。为此,他选择两个整数 $$$l \le r$$$ 并删除除 $$$v$$$ 和 $$$l \le v \le r$$$ 之外的所有顶点,并删除除剩余顶点之间的所有边。

现在仗助想知道$$$G'$$$中有多少种不同的重量。由于他们的数量巨大,他请求你的帮助。

$$$^\dagger$$$ 完全图是一个简单的无向图,其中每对不同的顶点都是相邻的。

$$$^\ddagger$$$ $$$\gcd(x, y)$$$ 表示数字 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个数字 $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$l \le 10^9$$$)。

输出

对于每个测试用例,打印一个数字 - 剩余边缘之间不同权重的数量。

示例

输入 #1

7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090

输出 #1

2
6
3
5
0
5
50045

注意

第一个测试用例的图表$$$G'$$$。

上图显示该图有 $$$2$$$ 不同的权重。

在第五个测试用例中,只有一个没有边源自的顶点,因此答案是 $$$0$$$。