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$$$。