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