Description

数字之王大赛今天正式开始。

游戏规则是这样的：

• 一个好的数字 $x$ 要满足 $x\%\lfloor\sqrt x\rfloor==0$
• 求 $l$ 到 $r$ 内有多少个好的数字，包含 $l,r$

游戏规则非常简单，请你写个程序来解答吧

Input Format

有 $T(1\le T\le 1E5)$ 组样例

对于每组样例

输入两个整数 $l,r(1\le l,r\le 1E18,l\le r)$

Output Format

对于每组样例在单独一行输出一个整数表示答案

5
8 19
8 20
119 121
1 100000000000000000
1234567891011 1000000000000000000

5
6
2
948683296
2996666667

Source

Online Judge http://127.0.0.1