CF1737B.Ela's Fitness and the Luxury Number

While working at DTL, Ela is very aware of her physical and mental health. She started to practice various sports, such as Archery, Yoga, and Football.

Since she started engaging in sports activities, Ela switches to trying a new sport on days she considers being "Luxury" days. She counts the days since she started these activities, in which the day she starts is numbered as day $1$. A "Luxury" day is the day in which the number of this day is a luxurious number.

An integer $x$ is called a luxurious number if it is divisible by ${\lfloor \sqrt{x} \rfloor}$.

Here $\lfloor r \rfloor$ denotes the "floor" of a real number $r$. In other words, it's the largest integer not greater than $r$.

For example: $8$, $56$, $100$ are luxurious numbers, since $8$ is divisible by $\lfloor \sqrt{8} \rfloor = \lfloor 2.8284 \rfloor = 2$, $56$ is divisible $\lfloor \sqrt{56} \rfloor = \lfloor 7.4833 \rfloor = 7$, and $100$ is divisible by $\lfloor \sqrt{100} \rfloor = \lfloor 10 \rfloor = 10$, respectively. On the other hand $5$, $40$ are not, since $5$ are not divisible by $\lfloor \sqrt{5} \rfloor = \lfloor 2.2361 \rfloor = 2$, and $40$ are not divisible by $\lfloor \sqrt{40} \rfloor = \lfloor 6.3246 \rfloor = 6$.

Being a friend of Ela, you want to engage in these fitness activities with her to keep her and yourself accompanied (and have fun together, of course). Between day $l$ and day $r$, you want to know how many times she changes the activities.

在 DTL 工作期间，Ela 非常注重自己的身体与心理健康。她开始尝试多种体育运动，例如射箭（Archery）、瑜伽（Yoga）和足球（Football）。

自从开始参与这些体育活动以来，Ela 会在她认定为“奢华日”（Luxury day）的那些天更换所练习的新运动项目。她从开始参与这些活动起对天数进行计数，起始当天记为第 $1$ 天。“奢华日”即该天的编号是一个“奢华数”（luxurious number）。

一个整数 $x$ 被称为奢华数，当且仅当它能被 $\lfloor \sqrt{x} \rfloor$ 整除。

其中 $\lfloor r \rfloor$ 表示实数 $r$ 的“下取整”（floor），即不超过 $r$ 的最大整数。

例如：$8$、$56$、$100$ 均为奢华数，因为 $8$ 可被 $\lfloor \sqrt{8} \rfloor = \lfloor 2.8284 \rfloor = 2$ 整除；$56$ 可被 $\lfloor \sqrt{56} \rfloor = \lfloor 7.4833 \rfloor = 7$ 整除；$100$ 可被 $\lfloor \sqrt{100} \rfloor = \lfloor 10 \rfloor = 10$ 整除。而 $5$ 和 $40$ 则不是奢华数，因为 $5$ 不能被 $\lfloor \sqrt{5} \rfloor = \lfloor 2.2361 \rfloor = 2$ 整除，且 $40$ 不能被 $\lfloor \sqrt{40} \rfloor = \lfloor 6.3246 \rfloor = 6$ 整除。

作为 Ela 的朋友，你希望与她一同参与这些健身活动，陪伴她（当然也一起享受乐趣）。现在，请你计算在第 $l$ 天到第 $r$ 天（含端点）之间，她共更换了多少次运动项目。

Each test contains multiple test cases. The first line has the number of test cases $t$ ($1 \le t \le 10\ 000$). The description of the test cases follows.

The only line of each test case contains two integers $l$ and $r$ ($1 \le l \le r \le 10^{18}$) — the intervals at which you want to know how many times Ela changes her sports.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10\ 000$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 10^{18}$）——表示你想知道 Ela 在该区间内更改运动项目的次数。

For each test case, output an integer that denotes the answer.

对于每个测试用例，输出一个表示答案的整数。

In the first test case, $5$ luxury numbers in range $[8, 19]$ are: $8, 9, 12, 15, 16$.

在第一个测试用例中，区间 $[8, 19]$ 内的 $5$ 个奢华数为：$8, 9, 12, 15, 16$。