题目描述

编写程序，要求多次查询 $[l,r]$ 范围内的完全平方数个数。定义整数 $x$ 为完全平方数：当且仅当可以找到整数 $y$ 使得 $y*y=x$。

输入格式

第一行一个数 $n(1 \le n \le 100000)$ 表示查询次数，之后 $n$ 行每行两个数 $l,r(1 \le 1 \le r \le 1000000000)$。

输出格式

对于每个查询，输出一个数表示答案。

样例

5
1 3
1 4
2 4
4 4
1 1000000000

1
2
1
1
31622