在 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$$$。