SP21176 TAP2014I - Stapled intervals

如果两个自然数 **n** 和 **m** 的最大公约数是 **1**，那么它们称为 _互质_。换句话说，只有当不存在一个整数 **d > 1** 能同时整除 **n** 和 **m** 时，这两个数才是互质的。当我们有一个由两个或多个连续自然数组成的有限集合时，如果在这个集合中没有任何一个数与集合中的其他所有数都互质，那么这个集合称为“钉子区间”。 给定一个范围 **\[A, B\]**，我们希望找出完全位于这个范围内的钉子区间的数量。具体来说，就是计算有多少不同的二元组 **(a, b)** 满足 **A ≤ a < b ≤ B** 并且 **{a, a+1, ..., b}** 是一个钉子区间。

第一行输入一个整数 **P**，代表需要回答的问题数量（$1 \le P \le 1000$）。接下来的 **P** 行，每行包含两个整数 **A** 和 **B**，表示需要计算钉子区间数量的范围 **\[A, B\]**（$1 \le A \le B \le 10^7$）。

输出 **P** 行，每行对应一个问题的答案。对于每个问题 **i = 1, 2, ..., P**，输出第 **i** 行表示在范围 **\[A, B\]** 内可以找到的钉子区间的数量。 **本翻译由 AI 自动生成**