该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于正整数 $x$，记 $\lfloor \sqrt{x} \rfloor$ 为对 $x$ 开平方后向下取整的结果。 如果 $\lfloor \sqrt{x} \rfloor$ 能整除 $x$，就称 $x$ 是一个奢华数。

33DAI 想知道：对于给定的 $t$ 个区间 $[l, r]$，每个区间内有多少个奢华数。

输入格式

从文件 luxury.in 读入数据。

第一行包含一个整数 $t$，表示询问的个数。

接下来 $t$ 行，每行包含两个整数 $l$ 与 $r$，表示一个询问区间 $[l, r]$。

输出格式

输出到文件 luxury.out。

对于每个询问输出一行一个整数，表示区间 $[l, r]$ 内奢华数的个数。

5
8 19
8 20
119 121
1 100000000000000000
1234567891011 1000000000000000000

5
6
2
948683296
2996666667

样例 1 解释

区间 $[8, 19]$ 内的奢华数是 $8, 9, 12, 15, 16$，共 $5$ 个；$[8, 20]$ 内再算上 $20$，共 $6$ 个； $[119, 121]$ 内有 $120$ 与 $121$，共 $2$ 个。后两个区间很大，按同样的定义统计， 个数分别是 $948683296$ 与 $2996666667$。

样例 2

见 luxury2.in 与 luxury2.ans。

样例 3

见 luxury3.in 与 luxury3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le t \le 10^4$；
• $1 \le l \le r \le 10^{18}$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。