← 返回题目列表

Codeforces · 1737/B

B. Ela 的健身与奢华数字

中文机器翻译题面 查看原题

在 DTL 工作期间,Ela 非常了解自己的身心健康状况。她开始练习各种运动,如射箭、瑜伽和足球。

自从开始从事体育活动后,Ela 在她认为“奢侈”的日子里转而尝试一项新运动。她计算了自开始这些活动以来的天数,其中她开始的那一天编号为 $$$1$$$。 “奢侈”日是指这一天的数字是奢侈数字的一天。

如果整数 $$$x$$$ 能被 $$${\lfloor \sqrt{x} \rfloor}$$$ 整除,则该整数称为豪华数。

这里 $$$\lfloor r \rfloor$$$ 表示实数 $$$r$$$ 的“下限”。换句话说,它是不大于$$$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$$$ 之间,您想知道她更改活动的次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\ 000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — 您想知道 Ela 改变运动项目的时间间隔。

输出

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

示例

输入 #1

5
8 19
8 20
119 121
1 100000000000000000
1234567891011 1000000000000000000

输出 #1

5
6
2
948683296
2996666667

注意

在第一个测试用例中,$$$[8, 19]$$$ 范围内的 $$$5$$$ 豪华号码为:$$$8, 9, 12, 15, 16$$$。