Josuke and Complete Graph

题意翻译

### 题目描述 Josuke 收到了一个巨大的无向带权完全图 $G$ 作为他祖父的礼物。该图形包含$10^{18}$ 个顶点。 这个礼物的特点是不同顶点 $u$ 和 $v$ 之间的边的权重等于 $\gcd(u,v)$ 。 Josuke 决定制作一个新的图 $G'$。为此，他选择两个整数 $l\le r$ ，并删除除 $l\le v\le r$ 的顶点 $v$ 之外的所有顶点以及与其相连的边。 现在 Josuke 想知道 $G'$ 中有的边多少种不同的权重。 ### 输入格式 第 $1$ 行一个整数 $t\;(1\le t\le100)$ ，表示数据组数。 接下来 $t$ 行每行两个整数 $l,r\;(1\le l\le r\le10^{18},l\le10^9\;)$ ，表示一组数据中的 $l,r$ 。 ### 输出格式 每行一个整数，表示每组数据 $G'$ 中不同权重的边的数量。 Translated by @[w9095](https://www.luogu.com.cn/user/569235)

题目描述

Josuke received a huge undirected weighted complete $ ^\dagger $ graph $ G $ as a gift from his grandfather. The graph contains $ 10^{18} $ vertices. The peculiarity of the gift is that the weight of the edge between the different vertices $ u $ and $ v $ is equal to $ \gcd(u, v)^\ddagger $ . Josuke decided to experiment and make a new graph $ G' $ . To do this, he chooses two integers $ l \le r $ and deletes all vertices except such vertices $ v $ that $ l \le v \le r $ , and also deletes all the edges except between the remaining vertices. Now Josuke is wondering how many different weights are there in $ G' $ . Since their count turned out to be huge, he asks for your help. $ ^\dagger $ A complete graph is a simple undirected graph in which every pair of distinct vertices is adjacent. $ ^\ddagger $ $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the numbers $ x $ and $ y $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case contains two numbers $ l $ , $ r $ ( $ 1 \le l \le r \le 10^{18} $ , $ l \le 10^9 $ ).

输出格式

For each test case print a single number — the number of different weights among the remaining edges.

输入输出样例

输入样例 #1

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

输出样例 #1

2
6
3
5
0
5
50045

说明

 The graph $ G' $ for the first test case.The picture above shows that the graph has $ 2 $ different weights. In the fifth test case, there is only one vertex from which no edges originate, so the answer is $ 0 $ .

题意翻译

### 题目描述 Josuke 收到了一个巨大的无向带权完全图 $G$ 作为他祖父的礼物。该图形包含$10^{18}$ 个顶点。 这个礼物的特点是不同顶点 $u$ 和 $v$ 之间的边的权重等于 $\gcd(u,v)$ 。 Josuke 决定制作一个新的图 $G'$。为此，他选择两个整数 $l\le r$ ，并删除除 $l\le v\le r$ 的顶点 $v$ 之外的所有顶点以及与其相连的边。 现在 Josuke 想知道 $G'$ 中有的边多少种不同的权重。 ### 输入格式 第 $1$ 行一个整数 $t\;(1\le t\le100)$ ，表示数据组数。 接下来 $t$ 行每行两个整数 $l,r\;(1\le l\le r\le10^{18},l\le10^9\;)$ ，表示一组数据中的 $l,r$ 。 ### 输出格式 每行一个整数，表示每组数据 $G'$ 中不同权重的边的数量。 Translated by @[w9095](https://www.luogu.com.cn/user/569235)