#P143. 完全平方数的个数

完全平方数的个数

题目描述

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

输入格式

第一行一个数 n(1n100000)n(1 \le n \le 100000) 表示查询次数,之后 nn 行每行两个数 l,r(11r1000000000)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