SP12352 HNUMBERS - HNumbers

Ualter 是一个热爱数学的小伙子，数字的一切都能吸引他的注意。最近，他的朋友 Matheus Pheverso 介绍了一类叫做 H-数的特别数字。Matheus 告诉他，在古希腊，H-数曾用来创作音乐。这类数字有如下定义： 给定一个整数 $N$，如果正整数 $A$ 满足以下条件： - 其最小公倍数 $\text{LCM}(N, A) = N \times A$ 那么我们称 $A$ 为 $N$ 的 H-数。 例如： - 对于 $N = 20$，H-数包括 $\{1, 3, 7, 9, 11, 13, 17, 19\}$ - 对于 $N = 10$，H-数为 $\{1, 3, 7, 9\}$ Ualter 对古典音乐尤其是帕赫贝尔的作品充满热爱。为了实现自己用 H-数创作《D 大调卡农》的梦想，他需要找到对于每个数字 $N$，在 $1$ 到 $M$ 之间的所有 H-数的数量。 任务： 你需要解决以下问题：给定整数 $Q$，每次查询中包含两个数 $N$ 和 $M$，你需要找出 $N$ 在 $1$ 到 $M$ 之间的 H-数的数量。

第一行输入一个整数 $Q$ ($1 \le Q \le 10^5$)，表示查询次数。接下来的 $Q$ 行中，每行输入两个整数 $N$ 和 $M$ ($1 \le N, M \le 10^5$, 且 $M < N$)。

对于每一条查询，输出一个整数 $x_i$，表示在 $1$ 到 $M$ 范围内 $N$ 的 H-数的数量。 **本翻译由 AI 自动生成**