题目描述

今天，小 John 用全部积蓄购买了一个区间。他想在这个区间上建造房屋。一个正整数区间 $[l, r]$ 被称为互质区间，当且仅当 $l$ 和 $r$ 互质$^{\text{∗}}$。

一个互质区间 $[l, r]$ 被称为最小互质区间，当且仅当它不包含$^{\text{†}}$任何不同于自身的互质子区间。为了更好地理解这个定义，可以参考说明部分的示例。

给定一个正整数区间 $[l, r]$，请计算其中包含的最小互质区间的数量。

$^{\text{∗}}$ 两个整数 $a$ 和 $b$ 互质当且仅当它们的最大公约数为 $1$。例如，$2$ 和 $4$ 不互质（它们的公约数包括 $1$ 和 $2$），而 $7$ 和 $9$ 互质（唯一公约数是 $1$）。

$^{\text{†}}$ 当且仅当 $l \le l' \le r' \le r$ 时，区间 $[l', r']$ 被称为包含于区间 $[l, r]$ 中。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 100$）。接下来描述各个测试用例。

每个测试用例占一行，包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 10^9$）。

输出格式

对于每个测试用例，单独输出一行，表示区间 $[l, r]$ 中包含的最小互质区间的数量。

说明/提示

第一个测试用例中，给定区间为 $[1, 2]$。其包含的子区间如下：

• $[1, 1]$：该区间是互质的，且不包含其他互质子区间，因此是最小互质区间。
• $[1, 2]$：该区间互质，但包含 $[1, 1]$ 这个互质子区间，因此不是最小互质区间。
• $[2, 2]$：该区间不互质（$\gcd(2,2)=2$）。

因此，区间 $[1, 2]$ 中包含 $1$ 个最小互质区间。

翻译由 DeepSeek R1 完成

样例

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

1
9
0
351
1
34371