UOJ Logo

NOI.AC

1S 512MB

#1291. 平方数的个数

Statistics

Description

完全平方数总是有神奇的性质。

灭霸在还没有集齐原石的时候,还是个菜鸡。这个菜鸡每天就思考怎么才能偷到足够厉害的宝贝。 终于有一天,他发现有一个星系非常特殊,这个星系中的星球全部以自然数按顺序从$1$开始命名,并且每个完全平方数的星球都保存着一个非常厉害的宝贝!

现在他有一个很低级的武器,能够征服连续编号的星球,并获得这些宝贝。

他想知道,编号从$L$到$R$的一段星球中,有多少个宝贝。

Input

第一行一个$T$,表示有$T$组测试数据。 接下来$T(0 \lt T \leq 50)$行,每行两个数字,$L,R(0 \lt L \leq R \leq 10^{18})$

Output

对于每组测试数据,输出一个整数,表示闭区间$L$到$R$这一段中的宝贝数。

Sample Input

2
1 4
5 10

Sample Output

2
1